Finite Size Corrections and Likelihood Ratio Fluctuations in the Spiked Wigner Model

Abstract

In this paper we study principal components analysis in the regime of high dimensionality and high noise. Our model of the problem is a rank-one deformation of a Wigner matrix where the signal-to-noise ratio (SNR) is of constant order, and we are interested in the fundamental limits of detection of the spike. Our main goal is to gain a fine understanding of the asymptotics for the log-likelihood ratio process, also known as the free energy, as a function of the SNR. Our main results are twofold. We first prove that the free energy has a finite-size correction to its limit—the replica-symmetric formula—which we explicitly compute. This provides a formula for the Kullback-Leibler divergence between the planted and null models. Second, we prove that below the reconstruction threshold, where it becomes impossible to reconstruct the spike, the log-likelihood ratio has fluctuations of constant order and converges in distribution to a Gaussian under both the planted and (under restrictions) the null model. As a consequence, we provide a general proof of contiguity between these two distributions that holds up to the reconstruction threshold, and is valid for an arbitrary separable prior on the spike. Formulae for the total variation distance, and the Type-I and Type-II errors of the optimal test are also given. Our proofs are based on Gaussian interpolation methods and a rigorous incarnation of the cavity method, as devised by Guerra and Talagrand in their study of the Sherrington-Kirkpatrick spin-glass model.

1 Introduction

Spiked models, which are distributions over matrices of the form “signal + noise,” have been a mainstay in the statistical literature since their introduction by Johnstone, (2001) as models for the study of high-dimensional principal component analysis that are tractable yet realistic. Spectral properties of these models have been extensively studied, in particular in random matrix theory, where they are known as deformed ensembles (Péché, , 2014). Landmark investigations in this area (Baik et al., , 2005; Baik and Silverstein, , 2006; Péché, , 2006; Féral and Péché, , 2007; Capitaine et al., , 2009) have established the existence of a spectral threshold above which the top eigenvalue detaches from the bulk of eigenvalues and becomes informative about the spike, and below which the top eigenvalue bears no information. Estimation using the top eigenvector undergoes the same transition, where it is known to “lose track” of the spike below the spectral threshold (Paul, , 2007; Nadler, , 2008; Johnstone and Lu, , 2009; Benaych-Georges and Nadakuditi, , 2011). Although these spectral analyses have provided many insights, as have analyses based on more thoroughgoing usage of spectral data and/or more advanced optimization-based procedures (see Amini and Wainwright, , 2009; Berthet and Rigollet, , 2013; Onatski et al., , 2013, 2014; Dobriban, , 2017, and references therein), they stop short of characterizing the fundamental limits of estimating the spike, or detecting its presence from the observation of a sample matrix. These questions, information-theoretic and statistical in nature, are more naturally approached by looking at objects such as the posterior law of spike and the associated likelihood ratio process.

The main approach to date to the challenging problem of controlling the likelihood ratio is via the second moment method. Controlling the second moment enables one to show contiguity, in the sense of Le Cam, (1960), between the planted and null models and thus declare impossibility of strong detection—i.e., the impossibility of vanishing Type-I and Type-II errors of any given test—in the region where this second moment is bounded (Banks et al., , 2017; Perry et al., , 2016). This method is known, however, to require careful conditioning and truncation due to the existence of rare but catastrophic events under which the likelihood ratio becomes exponentially large. These events thus dominate the second moment, although they are virtually irrelevant to the detection task. Moreover, even after conditioning the method may fail in identifying the detection thresholds, depending on the structure of the spike. Furthermore, contiguity has little or no bearing on the problem of weak detection: When errors are inevitable, what is the smallest error achievable by any test?

Motivated by a desire to overcome these limitations, we consider a particularly simple spiked model—the rank-one spiked Wigner model—and provide an alternative approach to the detection problem that obviates the use of the second moment method altogether. This is achieved by obtaining asymptotic distributional results for the log-likelihood ratio process, then appealing to standard results from the theory of statistical experiments. We are thereby able to provide solutions to both the strong and weak variants of the detection problem. To study the likelihood ratio in this setting we build on the technology developed by Aizenman, Guerra, Panchenko, Talagrand, and many others, in their study of the Sherrington-Kirkpatrick (SK) spin glass-model. Specifically, we make use of Gaussian interpolation methods and Talagrand’s cavity method.

1.1 Setup and summary of the results

In the spiked Wigner model, one observes a rank-one deformation of a Wigner matrix ${\bm{W}}$:

$$\bm{Y}=\sqrt{\frac{\lambda}{N}}\bm{x}^{*}\bm{x}^{*\top}+\bm{W},$$ (1)

where $W_{ij}=W_{ji}\sim\mathcal{N}(0,1)$ and $W_{ii}\sim\mathcal{N}(0,2)$ are independent for all $1\leq i\leq j\leq N$. The spike vector $\bm{x}^{*}\in\mathbb{R}^{N}$ represents the signal to be recovered, or its presence detected. We assume that the entries $x^{*}_{i}$ of the spike are drawn i.i.d. from a prior distribution $P_{\textup{{x}}}$ on $\mathbb{R}$ having bounded support. The parameter $\lambda\geq 0$ plays the role of the signal-to-noise ratio, and the scaling by $\sqrt{N}$ is such that the signal and noise components of the observed data are of comparable magnitudes. This places the problem in a high-noise regime where consistency is not possible but partial recovery still is. As a matter of convenience, we discard the diagonal terms $Y_{ii}$ from the observations. (Adding the diagonal back does not pose any additional technical difficulties, and our results can be straightforwardly extended to this case.) We endow the real line with the Borel $\sigma$-algebra and define $P_{\textup{{x}}}$ on it. We denote by $\operatorname{\mathbb{P}}_{\lambda}$ the joint probability law of the observations $\bm{Y}=\{Y_{ij}:1\leq i<j\leq N\}$ as per (1) and define the likelihood ratio

$$L(\bm{Y};\lambda):=\frac{\mathrm{d}\mathbb{P}_{\lambda}}{\mathrm{d}\mathbb{P}_{0}}(\bm{Y}).$$ (2)

A simple computation based on conditioning on $\bm{x}^{*}$ reveals that

$$L(\bm{Y};\lambda)=\int\exp\Big{(}\sqrt{\frac{\lambda}{N}}\sum_{i<j}Y_{ij}x_{i}x_{j}-\frac{\lambda}{2N}\sum_{i<j}x_{i}^{2}x_{j}^{2}\Big{)}~{}\mathrm{d}P_{\textup{{x}}}^{\otimes N}(\bm{x}).$$ (3)

We define the free energy (density) associated with the model $\operatorname{\mathbb{P}}_{\lambda}$ to be

$$F_{N}:=\frac{1}{N}\operatorname{\mathbb{E}}_{\operatorname{\mathbb{P}}_{\lambda}}\log L(\bm{Y};\lambda).$$ (4)

We see that $F_{N}=\frac{1}{N}D_{\mathsf{KL}}(\operatorname{\mathbb{P}}_{\lambda},\operatorname{\mathbb{P}}_{0})$, where $D_{\mathsf{KL}}$ is the Kullback-Leibler divergence between probability measures. (The free energy is usually defined differently in the literature as the log-normalizing constant in the posterior of $\bm{x}^{*}$ given $\bm{Y}$. The two definitions are strictly equivalent.) It was initially argued via heuristic replica and cavity computations (Lesieur et al., , 2015, 2017) that $F_{N}$ converges to a limit $\phi_{\mathsf{RS}}(\lambda)$, which is referred to as the replica-symmetric formula. This formula, variational in nature, encodes in principle a full characterization of the limits of estimating the spike with non-trivial accuracy. Indeed, various formulae for other information-theoretic quantities can be deduced from it, including the mutual information between $\bm{x}^{*}$ and $\bm{Y}$, the minimal mean squared error of estimating $\bm{x}^{*}$ based on $\bm{Y}$, and the overlap $|\bm{x}^{\top}\bm{x}^{*}|/N$ of a draw $\bm{x}$ from the posterior $\operatorname{\mathbb{P}}_{\lambda}(\cdot|\bm{Y})$ with the spike $\bm{x}^{*}$. Most of these claims have subsequently been proved rigorously in a series of papers (Deshpande and Montanari, , 2014; Deshpande et al., , 2016; Barbier et al., , 2016; Krzakala et al., , 2016; Lelarge and Miolane, , 2016) under various assumptions on the prior. However, these results stop short of providing explicit characterizations of thresholds for the detection problem.

The main goal of this paper is to gain a more refined understanding of the asymptotic behavior of the log-likelihood ratio $\log L(\bm{Y};\lambda)$, and its mean $NF_{N}$, under $\operatorname{\mathbb{P}}_{\lambda}$ as $N$ becomes large. We first determine the finite-size correction of $F_{N}$ to its limit $\phi_{\mathsf{RS}}(\lambda)$: we prove (under conditions on $P_{\textup{{x}}}$) that $N(F_{N}-\phi_{\mathsf{RS}}(\lambda))$ converges to a limit $\psi_{\mathsf{RS}}(\lambda)$ with rate $\mathcal{O}(1/\sqrt{N})$. Besides providing an explicit rate of convergence of $F_{N}$ to its limit, this result translates into a formula for the Kullback-Leibler divergence $D_{\mathsf{KL}}$, which is particularly interesting below the reconstruction threshold: we will see that in this regime $\phi_{\mathsf{RS}}(\lambda)=0$, so $D_{\mathsf{KL}}$ ceases to be extensive in the size of the system and converges to a finite value $\psi_{\mathsf{RS}}(\lambda)$.

Second, we prove that in this same regime, the log-likelihood ratio $\log L(\bm{Y};\lambda)$ has fluctuations of constant order under $\operatorname{\mathbb{P}}_{\lambda}$, and converges asymptotically to a Gaussian with a mean equal to half the variance. This allows us to provide an alternative proof of contiguity between $\operatorname{\mathbb{P}}_{\lambda}$ and $\operatorname{\mathbb{P}}_{0}$, valid in the entire regime where contiguity can possibly hold, as well as a formula for the Type-II error for testing between these two distributions.

Under the null distribution $\operatorname{\mathbb{P}}_{0}$ on the other hand, the model is equivalent to the widely studied Sherrington-Kirkpatrick model (provided that $P_{\textup{{x}}}=\frac{1}{2}\delta_{-1}+\frac{1}{2}\delta_{+1}$). In one of the first rigorous results on this model, Aizenman et al., (1987) proved that in the high-temperature regime and in the absence of an external field, the fluctuations of the log-partition function of the model about its mean, which is given by the “annealed” computation, are asymptotically Gaussian with explicit mean and variance. By mapping their result into our setting, we obtain the fluctuations of $\log L(\bm{Y};\lambda)$ under $\operatorname{\mathbb{P}}_{0}$ in the non-reconstruction phase, as well as a formula for the Type-I error. Although we only obtain this last formula for the Rademacher prior, we conjecture its validity for arbitrary priors. An interesting symmetry emerges from these results: the limiting Gaussians under $\operatorname{\mathbb{P}}_{\lambda}$ and $\operatorname{\mathbb{P}}_{0}$ have means of equal magnitude and opposite signs, and equal variances. This symmetry causes the Type-I and Type-II errors to be equal. Adding up the two latter quantities, we obtain a formula for the total variation distance $D_{\mathsf{TV}}(\operatorname{\mathbb{P}}_{\lambda},\operatorname{\mathbb{P}}_{0})$.

Our results are in the spirit of those of Onatski et al., (2013, 2014), who studied the likelihood ratio of the joint eigenvalue densities under the spiked covariance model with a sphericity prior, and showed its asymptotic normality below the spectral threshold. Their results thus pertain to eigenvalue-based tests while ours are for arbitrary tests, albeit for a simpler model. Our results show in particular that it is still possible to distinguish the planted model $\operatorname{\mathbb{P}}_{\lambda}$ from the null model $\operatorname{\mathbb{P}}_{0}$ with non-vanishing probability below the reconstruction threshold; i.e., even when estimation of the spike $\bm{x}^{*}$ becomes impossible. Performing such a test in practice of course hinges on the computational problem of efficiently computing the likelihood ratio; we leave open this question of constructing computationally efficient tests in the non-reconstruction phase.

1.2 Background

The $\mathsf{RS}$ formula.

For $r\geq 0$, consider the function

$$\psi(r):=\operatorname{\mathbb{E}}_{x^{*},z}\log\int\exp\left(\sqrt{r}zx+rxx^{*}-\frac{r}{2}x^{2}\right)\mathrm{d}P_{\textup{{x}}}(x),$$ (5)

where $z\sim\mathcal{N}(0,1)$, and $x^{*}\sim P_{\textup{{x}}}$. This is the $\mathsf{KL}$ divergence between the distributions of the random variables $y=\sqrt{r}x^{*}+z$ and $z$. We define the Replica-Symmetric ($\mathsf{RS}$) potential

$$F(\lambda,q):=\psi(\lambda q)-\frac{\lambda q^{2}}{4},$$ (6)

and finally define the $\mathsf{RS}$ formula

$$\phi_{\mathsf{RS}}(\lambda):=\sup_{q\geq 0}~{}F(\lambda,q).$$ (7)

A central result in this context is that free energy $F_{N}$ converges to the $\mathsf{RS}$ formula for all $\lambda\geq 0$  (Lesieur et al., , 2015, 2017; Deshpande et al., , 2016; Barbier et al., , 2016; Krzakala et al., , 2016; Lelarge and Miolane, , 2016):

$$F_{N}~{}~{}\longrightarrow~{}~{}\phi_{\mathsf{RS}}(\lambda).$$

The values of $q$ that maximize the $\mathsf{RS}$ potential and their properties play an important role in the theory. Lelarge and Miolane, (2016) proved that the map $q\mapsto F(\lambda,q)$ has a unique maximizer $q^{*}=q^{*}(\lambda)$ for all $\lambda\in\mathcal{D}$ where $\mathcal{D}$ is the set of points where the function $\lambda\mapsto\phi_{\mathsf{RS}}(\lambda)$ is differentiable. By convexity of $\phi_{\mathsf{RS}}$ (see next section), $\mathcal{D}=\mathbb{R}_{+}\setminus\mbox{countable set}$. Moreover, they showed that the map $\lambda\in\mathcal{D}\mapsto q^{*}(\lambda)$ is non-decreasing, and

$$\lim_{\underset{\lambda\in\mathcal{D}}{\lambda\to 0}}q^{*}(\lambda)=\operatorname{\mathbb{E}}_{P_{\textup{{x}}}}[X]^{2},\qquad\text{and}\qquad\lim_{\underset{\lambda\in\mathcal{D}}{\lambda\to\infty}}q^{*}(\lambda)=\operatorname{\mathbb{E}}_{P_{\textup{{x}}}}[X^{2}].$$ (8)

One should interpret the value $q^{*}(\lambda)$ as the best overlap an estimator $\widehat{\theta}(\bm{Y})$ based on observing $\bm{Y}$ can have with the spike $\bm{x}^{*}$. Indeed, the overlap $\big{|}\bm{x}^{\top}\bm{x}^{*}\big{|}/N$ between the spike $\bm{x}^{*}$ and a random draw $\bm{x}$ from the posterior $\operatorname{\mathbb{P}}_{\lambda}(\cdot|\bm{Y})$ should concentrate in the large $N$ limit about $q^{*}(\lambda)$ (hence the name “replica-symmetry”). A matrix variant of this result (where one estimates $\bm{x}^{*}\bm{x}^{*\top}$) was proved in (Lelarge and Miolane, , 2016). In Section 3, we prove strong (vector) versions of this result where under mild assumptions, optimal rates of convergence are given.

The reconstruction threshold.

The first limit in (8) shows that when the prior $P_{\textup{{x}}}$ is not centered, it is always possible to have a non-trivial overlap with $\bm{x}^{*}$ for any $\lambda>0$. On the other hand, when the prior has zero mean, and since $q^{*}$ is a non-decreasing function of $\lambda$, it is useful to define the critical value of $\lambda$ below which estimating $\bm{x}^{*}$ becomes impossible:

$$\lambda_{c}:=\sup\big{\{}\lambda>0~{}:~{}q^{*}(\lambda)=0\big{\}}.$$ (9)

We refer to $\lambda_{c}$ as the critical or reconstruction threshold. The next lemma establishes a natural bound on $\lambda_{c}$.

Lemma 1.

We have

$$\lambda_{c}\cdot\left(\operatorname{\mathbb{E}}_{P_{\textup{{x}}}}[X^{2}]\right)^{2}\leq 1.$$ (10)

Proof.

Indeed, assume that $P_{\textup{{x}}}$ is centered, and let $\lambda>(\operatorname{\mathbb{E}}[X^{2}])^{-2}$. Since $\psi^{\prime}(0)=\frac{1}{2}\operatorname{\mathbb{E}}_{P_{\textup{{x}}}}[X]^{2}=0$ and $\psi^{\prime\prime}(0)=\frac{1}{2}(\operatorname{\mathbb{E}}_{P_{\textup{{x}}}}[X^{2}])^{2}$, we see that $\partial_{q}F(\lambda,0)=0$ and $\partial_{q}^{2}F(\lambda,0)=\frac{\lambda}{2}(\lambda\operatorname{\mathbb{E}}_{P_{\textup{{x}}}}[X^{2}]^{2}-1)>0$. So $q=0$ cannot be a maximizer of $F(\lambda,\cdot)$. Therefore $q^{*}(\lambda)>0$ and $\lambda\geq\lambda_{c}$. $\blacksquare$

The importance of Lemma 1 stems from the fact that the value $\left(\operatorname{\mathbb{E}}_{P_{\textup{{x}}}}[X^{2}]\right)^{-2}$ is the spectral threshold previously discussed. Above this value, the first eigenvalue of the matrix $\bm{Y}$ leaves the bulk, and is at the edge of the bulk below it (Péché, , 2006; Capitaine et al., , 2009; Féral and Péché, , 2007). This value also marks the limit below which the first eigenvector of $\bm{Y}$ captures no information about the spike $\bm{x}^{*}$ (Benaych-Georges and Nadakuditi, , 2011). Inequality (10) can be strict or turn into equality depending on the prior $P_{\textup{{x}}}$. For instance, there is equality if the prior is Gaussian or Rademacher—so that the first eigenvector overlaps with the spike as soon as estimation becomes possible at all—and strict inequality in the case of the (sufficiently) sparse Rademacher prior $P_{\textup{{x}}}=\frac{\rho}{2}\delta_{-1/\sqrt{\rho}}+(1-\rho)\delta_{0}+\frac{\rho}{2}\delta_{+1/\sqrt{\rho}}$. More precisely, there exists a value

$$\rho^{*}=\inf\big{\{}\rho\in(0,1)~{}:~{}\psi^{\prime\prime\prime}(0)<0\big{\}}\approx 0.092,$$

such that $\lambda_{c}=1$ for $\rho\geq\rho^{*}$, and $\lambda_{c}<1$ for $\rho<\rho^{*}$. In the latter case, the spectral approach to estimating $\bm{x}^{*}$ fails for $\lambda\in(\lambda_{c},1)$, and it is believed that no polynomial time algorithm succeeds in this region (Lesieur et al., , 2015; Krzakala et al., , 2016; Banks et al., , 2017).

2 Main results

2.1 Finite size corrections to the $\mathsf{RS}$ formula

The results we are about to present hold in a possibly slightly smaller set than $\mathcal{D}$. While uniqueness of $q^{*}$ only needs first differentiability of the $\mathsf{RS}$ formula, our results need a second derivative to exist. In physics parlance, our results do not hold at values of $\lambda$ at which a particular kind of first-order phase transition occurs, namely, one in which the order parameter $q^{*}$ is not differentiable. The presence of these transitions depends again on the prior $P_{\textup{{x}}}$. For the Gaussian and Rademacher prior, there are no such transitions, while for the sparse Rademacher prior discussed above, there is one first-order transition where $q^{*^{\prime}}$ is not defined for every $\rho<\rho^{*}$. Thus we define the set

$$\mathcal{A}=\big{\{}\lambda>0~{}:~{}\phi_{\mathsf{RS}}\mbox{ is twice differentiable at }\lambda.\big{\}}.$$

Since $\phi_{\mathsf{RS}}$ is the point-wise limit of a sequence $(F_{N})$ of convex functions, it is also convex. Then by Alexandrov’s theorem (Aleskandrov, , 1939), the set $\mathcal{A}$ is of full Lebesgue measure in $\mathbb{R}_{+}$ (cf. $\mathcal{D}=\mathbb{R}_{+}\setminus\mbox{countable set}$.) Moreover, we can see that $(0,\lambda_{c})\subset\mathcal{A}$, since if $\lambda\in\mathcal{A}\cap(0,\lambda_{c})$, we have $q^{*}(\lambda)=0$, therefore $\phi_{\mathsf{RS}}(\lambda)=0$. By continuity, $\phi_{\mathsf{RS}}$ vanishes on the entire interval $(0,\lambda_{c})$. Our first main result is to establish the existence of a function $\lambda\mapsto\psi_{\mathsf{RS}}(\lambda)$ defined on $\mathcal{A}$ such that either below $\lambda_{c}$ or above it when the prior $P_{\textup{{x}}}$ is not symmetric about the origin, we have

$$N(F_{N}-\phi_{\mathsf{RS}}(\lambda))\longrightarrow\psi_{\mathsf{RS}}(\lambda).$$

An explicit formula for $\psi_{\mathsf{RS}}$ will be given. But first we need to introduce some notation. Let $\lambda\in\mathcal{A}$ and consider the quantities

$$a(0)=\operatorname{\mathbb{E}}\left[\langle x^{2}\rangle_{r}^{2}\right]-q^{*2}(\lambda),\quad a(1)=\operatorname{\mathbb{E}}\left[\langle x^{2}\rangle_{r}\langle x\rangle_{r}^{2}\right]-q^{*2}(\lambda),\quad a(2)=\operatorname{\mathbb{E}}\left[\langle x\rangle_{r}^{4}\right]-q^{*2}(\lambda),$$ (11)

where

$$\langle\cdot\rangle_{r}=\frac{\int\cdot\exp\left(\sqrt{r}zx+rxx^{*}-\frac{r}{2}x^{2}\right)\mathrm{d}P_{\textup{{x}}}(x)}{\int\exp\left(\sqrt{r}zx+rxx^{*}-\frac{r}{2}x^{2}\right)\mathrm{d}P_{\textup{{x}}}(x)},$$

with $r=\lambda q^{*}(\lambda)$ and the expectation operator $\operatorname{\mathbb{E}}$ is w.r.t. $x^{*}\sim P_{\textup{{x}}}$ and $z\sim\mathcal{N}(0,1)$. The Gibbs measure $\langle\cdot\rangle_{r}$ can be interpreted as the posterior distribution of $x^{*}$ given the observation $y=\sqrt{r}x^{*}+z$. (More on this point of view in Section 3.) Now let

$$\begin{aligned} \mu_{1}(\lambda)&=\lambda(a(0)-2a(1)+a(2)),\\ \mu_{2}(\lambda)&=\lambda(a(0)-3a(1)+2a(2)),\end{aligned}$$ (12)

and finally define

$$\psi_{\mathsf{RS}}(\lambda):=\frac{1}{4}\left(\log(1-\mu_{1})-2\log(1-\mu_{2})+\lambda\frac{4a(1)-3a(2)}{1-\mu_{1}}-\lambda a(0)\right).$$ (13)

We will prove (Lemma 18) that $\mu_{2}\leq\mu_{1}<1$ for all $\lambda\in\mathcal{A}$ so that this function is well defined on $\mathcal{A}$.

Theorem 2.

For $\lambda\in\mathcal{A}$, if either $\lambda<\lambda_{c}$, or $\lambda>\lambda_{c}$ and the prior $P_{\textup{{x}}}$ is not symmetric about the origin, then

$$N\big{(}F_{N}-\phi_{\mathsf{RS}}(\lambda)\big{)}=\psi_{\mathsf{RS}}(\lambda)+\mathcal{O}\Big{(}\frac{1}{\sqrt{N}}\Big{)},$$

or equivalently, $D_{\mathsf{KL}}(\operatorname{\mathbb{P}}_{\lambda},\operatorname{\mathbb{P}}_{0})=N\phi_{\mathsf{RS}}(\lambda)+\psi_{\mathsf{RS}}(\lambda)+\mathcal{O}(1/\sqrt{N})$.

The theorem asserts that either below the reconstruction threshold, or above it when the prior $P_{\textup{{x}}}$ is not symmetric, the free energy $F_{N}$ has a finite-size correction of order $1/N$ to its limit $\phi_{\mathsf{RS}}$ and a subsequent term of order $N^{-3/2}$ in the expansion. In the case $\lambda>\lambda_{c}$ with symmetric prior, the problem is invariant under a sign flip of the spike, so the overlap $\bm{x}^{\top}\bm{x}^{*}/N$ has a symmetric distribution, and hence concentrates equiprobably about two distinct values $\pm q^{*}(\lambda)$. Our techniques do not survive this symmetry, and resolving this case seems to require a new approach.

We see that $D_{\mathsf{KL}}(\operatorname{\mathbb{P}}_{\lambda},\operatorname{\mathbb{P}}_{0})$ is an extensive quantity in $N$ whenever $\phi_{\mathsf{RS}}(\lambda)>0$, or equivalently, $\lambda>\lambda_{c}$. On the other hand, this $\mathsf{KL}$ is of constant order below $\lambda_{c}$:

Centered prior.

Let us consider the case where the prior $P_{\textup{{x}}}$ has zero mean, and unit variance (the latter can be assumed without loss of generality by rescaling $\lambda$), so that Lemma 1 reads $\lambda_{c}\leq 1$. If $\lambda<\lambda_{c}$, we have $q^{*}(\lambda)=0$, $\phi_{\mathsf{RS}}(\lambda)=0$, and one can check that in this case

$$a(0)=(\operatorname{\mathbb{E}}_{P_{\textup{{x}}}}[X^{2}])^{2}=1,\quad a(1)=\operatorname{\mathbb{E}}_{P_{\textup{{x}}}}[X^{2}]\operatorname{\mathbb{E}}_{P_{\textup{{x}}}}[X]^{2}=0,\quad a(2)=\operatorname{\mathbb{E}}_{P_{\textup{{x}}}}[X]^{4}=0.$$

Therefore, expression (13) simplifies to

$$\psi_{\mathsf{RS}}(\lambda)=\frac{1}{4}\left(-\log\left(1-\lambda\right)-\lambda\right).$$

By the above calculation, we have a formula for the $\mathsf{KL}$ divergence between $\operatorname{\mathbb{P}}_{\lambda}$ and $\operatorname{\mathbb{P}}_{0}$ below the reconstruction threshold $\lambda_{c}$ (see plot in Figure 1):

Corollary 3.

Assume the prior $P_{\textup{{x}}}$ is centered and of unit variance. Then for all $\lambda<\lambda_{c}$,

$$D_{\mathsf{KL}}(\operatorname{\mathbb{P}}_{\lambda},\operatorname{\mathbb{P}}_{0})=\frac{1}{4}\left(-\log\left(1-\lambda\right)-\lambda\right)+\mathcal{O}\Big{(}\frac{1}{\sqrt{N}}\Big{)}.$$ (14)

More information on $\psi_{\mathsf{RS}}$.

Expression (13) looks mysterious at first sight. Let us briefly explain its origin. A slightly less processed expression for $\psi_{\mathsf{RS}}$ is the following

$$\psi_{\mathsf{RS}}(\lambda)=\frac{1}{4}\int_{0}^{1}\left(-\frac{\mu_{1}}{1-t\mu_{1}}+\frac{2\mu_{2}}{1-t\mu_{2}}+\lambda\frac{4a(1)-3a(2)}{(1-t\mu_{1})^{2}}\right)\mathrm{d}t-\frac{\lambda}{4}a(0),$$

after which (13) follows by simple integration. The integrand in the above expression is obtained, as we will show, as the first entry $z(0)$ of the solution $\bm{z}=[z(0),z(1),z(2)]^{\top}$ of the $3\times 3$ linear system

$$(\bm{I}-t\bm{A})\bm{z}=\bm{a},$$

where $\bm{a}=[a(0),a(1),a(2)]^{\top}$ and $\bm{A}$ is the “cavity” matrix

$$\bm{A}:=\lambda\cdot\begin{bmatrix}a(0)&-2a(1)&a(2)\\ a(1)&a(0)-a(1)-2a(2)&-2a(1)+3a(2)\\ a(2)&4a(1)-6a(2)&a(0)-6a(1)+6a(2)\end{bmatrix}.$$

The above matrix happens to have two eigenvalues which are exactly $\mu_{1}$ and $\mu_{2}$. The matrix $\bm{A}$ and the above linear system will emerge naturally as a result of the cavity method. On the other hand, the integral over the time parameter $t$ is along an interpolation path invented by Guerra, (2001), (see also Guerra and Toninelli, 2002b, ) in the context of the Sherrington–Kirkpatrick model, and the integrand can be interpreted as the asymptotic variance in a central limit theorem satisfied by the overlap between two “replicas” under the law induced by a certain interpolating Gibbs measure. A definition of these notions with the corresponding results can be found in Sections 3 and 4. The full execution of the cavity method is relegated to Section 5.

2.2 Fluctuations below the reconstruction threshold

Corollary 14 asserts that below the reconstruction threshold, the expectation of the log-likelihood ratio $\log L(\bm{Y};\lambda)$ under $\operatorname{\mathbb{P}}_{\lambda}$ is of constant order (in $N$) and is asymptotically equal to $(-\log\left(1-\lambda\right)-\lambda)/4$. In this section we are interested in the fluctuations of this quantity about its expectation. It can be seen by a standard concentration-of-measure argument that for all $\lambda>0$, $\log L(\bm{Y};\lambda)$ concentrates about its expectation with fluctuations bounded by $\mathcal{O}(\sqrt{N})$. While this bound is likely to be of the right order above $\lambda_{c}$ (this is true for the SK model, see Guerra and Toninelli, 2002a, ), it is very pessimistic below $\lambda_{c}$. Indeed, we will show that the fluctuations are of constant order with a Gaussian limiting law in this regime. This phenomenon was noticed early on in the case of the SK model: Aizenman et al., (1987) showed that in the absence of an external field, the log-partition function of this model has (shifted) Gaussian fluctuations about its easily computed “annealed average” in high temperature. We will directly deduce from their result a central limit theorem for $\log L(\bm{Y};\lambda)$ under $\operatorname{\mathbb{P}}_{0}$ in the case where the prior $P_{\textup{{x}}}$ is Rademacher. Furthermore, a proof by Talagrand, 2011b of their result provided us with a road map for proving a similar result under $\operatorname{\mathbb{P}}_{\lambda}$. We now present our second main result along with consequences for hypothesis testing. For $\lambda<1$, let

$$\mu(\lambda)=\frac{1}{4}\left(-\log(1-\lambda)-\lambda\right),\qquad\mbox{and}\qquad\sigma^{2}(\lambda)={2\mu(\lambda)}.$$

Theorem 4.

Assume the prior $P_{\textup{{x}}}$ is centered and of unit variance.

• For all $\lambda<\lambda_{c}$, if $\bm{Y}\sim\operatorname{\mathbb{P}}_{\lambda}$ then

  $$\log L(\bm{Y};\lambda)\rightsquigarrow\mathcal{N}(\mu,\sigma^{2}).$$

• Under the additional condition $P_{\textup{{x}}}=\frac{1}{2}\delta_{-1}+\frac{1}{2}\delta_{+1}$, if $\bm{Y}\sim\operatorname{\mathbb{P}}_{0}$, then for all $\lambda<1$,

  $$\log L(\bm{Y};\lambda)\rightsquigarrow\mathcal{N}(-\mu,\sigma^{2}).$$

The symbol $``\rightsquigarrow"$ denotes convergence in distribution as $N\to\infty$. The formal connection to the SK model and the proof of the above theorem are presented in Section 6.

A remarkable feature is the symmetry between the above two statements. Roughly speaking, this symmetry takes its roots in the fact that the model under the alternative distribution $\operatorname{\mathbb{P}}_{\lambda}$ “lives on the Nishimori line”: under $\operatorname{\mathbb{P}}_{\lambda}$, which is the spiked model, the interaction of the spike $\bm{x}^{*}$ with a replica $\bm{x}^{(1)}$ creates terms that account for twice the contribution of the interaction between two independent replicas $\bm{x}^{(1)}$ and $\bm{x}^{(2)}$, and thus flips the sign of the mean from $-\mu$ to $\mu$. This mechanism will become apparent from the proof. Moreover, the fact that the mean is half the variance in these limiting Gaussians has interesting consequences for hypothesis testing. The next subsection is devoted to this problem.

We believe that statement (ii) is still valid up to $\lambda_{c}$ for a general prior (of zero mean and unit variance). It is possible to prove the convergence up to some value $\lambda_{0}\leq\lambda_{c}$ with essentially the same approach as ours, but reaching the optimal threshold seems to require more technical work. In particular, our interpolation bound (see our “main estimate”, section 4.2) has to be significantly improved to deal with this case. Progress will be reported in a future work.

We also point out that similar fluctuation results were recently proved by Baik and Lee, (2016, 2017) for a spherical model where one integrates over the uniform measure on the sphere in the definition of $L(\bm{Y};\lambda)$. Their model, due to its integrable nature, is amenable to analysis using tools from random matrix theory. The authors are thus able to also analyze a “low temperature” regime (absent in our problem) where the fluctuations are no longer Gaussian but given by the Tracy-Widom distribution. Their techniques seem to be tied to the spherical case however.

2.2.1 Strong and weak detection below $\lambda_{c}$.

Consider the problem of deciding whether an array of observations $\bm{Y}=\{Y_{ij}:1\leq i<j\leq N\}$ is likely to have been generated from $\operatorname{\mathbb{P}}_{\lambda}$ for a fixed $\lambda>0$ or from $\operatorname{\mathbb{P}}_{0}$. Let us denote by $\bm{H}_{0}:\bm{Y}\sim\operatorname{\mathbb{P}}_{0}$ the null hypothesis and $\bm{H}_{\lambda}:\bm{Y}\sim\operatorname{\mathbb{P}}_{\lambda}$ the alternative hypothesis. Two formulations of this problem exist: one would like to construct a sequence of measurable tests $T:\mathbb{R}^{N(N-1)/2}\mapsto\{0,1\}$ that returns “0” for ${\bm{H}}_{0}$ and “1” for ${\bm{H}}_{\lambda}$, for which either

$$\lim_{N\to\infty}~{}\max~{}\Big{\{}\operatorname{\mathbb{P}}_{\lambda}(T(\bm{Y})=0),~{}\operatorname{\mathbb{P}}_{0}(T(\bm{Y})=1)\Big{\}}=0,$$ (15)

or less stringently, the total mis-classification error, or risk

$$\mathsf{err}(T):=\operatorname{\mathbb{P}}_{\lambda}(T(\bm{Y})=0)+\operatorname{\mathbb{P}}_{0}(T(\bm{Y})=1)$$ (16)

is minimized among all possible tests $T$. The question of existence of a test that answers to the requirement (15) is referred to as the strong detection problem, and the question of minimizing the criterion (16) is referred to as the weak detection, or simply hypothesis testing problem.

Strong detection.

Using a second moment argument based on the computation of a truncated version of $\operatorname{\mathbb{E}}L(\bm{Y};\lambda)^{2}$, Banks et al., (2017) and Perry et al., (2016) showed that $\operatorname{\mathbb{P}}_{\lambda}$ and $\operatorname{\mathbb{P}}_{0}$ are mutually contiguous when $\lambda<\lambda_{0}$, where the latter quantity equals $\lambda_{c}$ for some priors $P_{\textup{{x}}}$ while it is suboptimal for others (e.g., the sparse Rademacher case, see discussion below). It is easy to see that contiguity implies impossibility of strong detection since for instance, if $\operatorname{\mathbb{P}}_{0}(T(\bm{Y})=1)\to 0$ then $\operatorname{\mathbb{P}}_{\lambda}(T(\bm{Y})=0)\to 1$. Here we show that Theorem 4 provides a more powerful approach to contiguity:

Corollary 5.

Assume the prior $P_{\textup{{x}}}$ is centered and of unit variance. Then for all $\lambda<\lambda_{c}$, $\operatorname{\mathbb{P}}_{\lambda}$ and $\operatorname{\mathbb{P}}_{0}$ are mutually contiguous.

Proof.

A consequence of statement (i) in Theorem 4 is that if

$$\frac{\mathrm{d}\operatorname{\mathbb{P}}_{0}}{\mathrm{d}\operatorname{\mathbb{P}}_{\lambda}}~{}{\rightsquigarrow}~{}U$$

under $\operatorname{\mathbb{P}}_{\lambda}$ along some subsequence and for some random variable $U$, then by the continuous mapping theorem we necessarily have

$$U=\exp\mathcal{N}(-\mu,\sigma^{2}).$$

We have $\Pr(U>0)=1$, and since $\mu=\frac{1}{2}\sigma^{2}$, we have $\operatorname{\mathbb{E}}U=1$. We now conclude using Le Cam’s first lemma in both directions (Lemma 6.4 or Example 6.5, Van der Vaart, , 2000). $\blacksquare$

This approach allows one to circumvent second moment computations which are not guaranteed to be tight in general, and necessitate careful and prior-specific conditioning that truncates away undesirable events.

We note that in the case of the sparse Rademacher prior $P_{\textup{{x}}}=\frac{\rho}{2}\delta_{-1/\sqrt{\rho}}+(1-\rho)\delta_{0}+\frac{\rho}{2}\delta_{+1/\sqrt{\rho}}$, contiguity holds for all $\lambda<1$ as soon as $\rho\geq\rho^{*}\approx 0.092$ by the above corollary, thus closing the gaps in the results of Banks et al., (2017) and Perry et al., (2016). Indeed, as argued below Lemma 1, the reconstruction and spectral thresholds are equal ($\lambda_{c}=1$) for all $\rho\geq\rho^{*}$, and differ ($\lambda_{c}<1$) below $\rho^{*}$. This implies that strong detection is impossible for $\lambda<1$ and possible otherwise when $\rho\geq\rho^{*}$, while it becomes impossible only below $\lambda_{c}$ but possible otherwise when $\rho<\rho^{*}$.

Weak detection.

We have seen that strong detection is possible if and only if $\lambda>\lambda_{c}$. It is then natural to ask whether weak detection is possible below $\lambda_{c}$, i.e., is it possible to test with accuracy better than that of a random guess below the reconstruction threshold? The answer is yes, and this is another consequence of Theorem 4. More precisely, the optimal test minimizing the risk (16) is the likelihood ratio test which rejects the null hypothesis $\bm{H}_{0}$ (i.e., returns “1”) if $L(\bm{Y};\lambda)>1$, and its error is

$$\mathsf{err}^{*}(\lambda)=\operatorname{\mathbb{P}}_{\lambda}(L(\bm{Y};\lambda)\leq 1)+\operatorname{\mathbb{P}}_{0}(L(\bm{Y};\lambda)>1)=1-D_{\mathsf{TV}}(\operatorname{\mathbb{P}}_{\lambda},\operatorname{\mathbb{P}}_{0}).$$ (17)

One can readily deduce from Theorem 4 the Type-I and Type-II errors of the likelihood ratio test: for all $\lambda<\lambda_{c}$ the Type-II error is

$$\operatorname{\mathbb{P}}_{\lambda}(\log L(\bm{Y};\lambda)\leq 0)=\int_{-\infty}^{0}\frac{1}{\sqrt{2\pi}}e^{-(t-\mu)^{2}/2\sigma^{2}}\mathrm{d}t+o_{N}(1)=\frac{1}{2}\mathsf{erfc}\left(\frac{\sqrt{\mu}}{2}\right)+o_{N}(1),$$

and in the case of the Rademacher prior, the Type-I error is

$$\operatorname{\mathbb{P}}_{0}(\log L(\bm{Y};\lambda)>0)=\int_{0}^{+\infty}\frac{1}{\sqrt{2\pi}}e^{-(t+\mu)^{2}/2\sigma^{2}}\mathrm{d}t+o_{N}(1)=\frac{1}{2}\mathsf{erfc}\left(\frac{\sqrt{\mu}}{2}\right)+o_{N}(1)$$

for all $\lambda<1$. Here, $\mathsf{erfc}(x)=\frac{2}{\sqrt{\pi}}\int_{x}^{\infty}e^{-t^{2}}\mathrm{d}t$ is the complementary error function. These can be combined into a formula for $\mathsf{err}^{*}(\lambda)$ and the total variation distance between $\operatorname{\mathbb{P}}_{\lambda}$ and $\operatorname{\mathbb{P}}_{0}$ (see plot in Figure 1):

Corollary 6.

Assume $P_{\textup{{x}}}=\frac{1}{2}\delta_{-1}+\frac{1}{2}\delta_{+1}$. For all $\lambda<1$, we have

$$\lim_{N\to\infty}\mathsf{err}^{*}(\lambda)=1-\lim_{N\to\infty}D_{\mathsf{TV}}(\operatorname{\mathbb{P}}_{\lambda},\operatorname{\mathbb{P}}_{0})=\mathsf{erfc}\left(\frac{\sqrt{\mu(\lambda)}}{2}\right).$$ (18)

We similarly conjecture that the formula for Type-I error, hence formula (18), should be correct up to $\lambda_{c}$ for all (bounded) priors with zero mean and unit variance.

Figure 1: Plots of formulas (18) and (14).

3 Overlap convergence: optimal rates

A crucial component of proving our main results is understanding the rate of convergence of the overlap $\bm{x}^{\top}\bm{x}^{*}/N$, where $\bm{x}$ is drawn from $\operatorname{\mathbb{P}}_{\lambda}(\cdot|\bm{Y})$, to its limit $q^{*}(\lambda)$. By Bayes’ rule, we see that

$$\mathrm{d}\operatorname{\mathbb{P}}_{\lambda}(\bm{x}|\bm{Y})=\frac{e^{-H(\bm{x})}\mathrm{d}P_{\textup{{x}}}^{\otimes N}(\bm{x})}{\int e^{-H(\bm{x})}\mathrm{d}P_{\textup{{x}}}^{\otimes N}(\bm{x})},$$ (19)

where $H$ is the Hamiltonian

$$-H(\bm{x}) :=-\frac{\lambda}{2N}\sum_{i<j}x_{i}^{2}x_{j}^{2}+\sqrt{\frac{\lambda}{N}}\sum_{i<j}Y_{ij}x_{i}x_{j}$$ (20)

$$=-\frac{\lambda}{2N}\sum_{i<j}x_{i}^{2}x_{j}^{2}+\sqrt{\frac{\lambda}{N}}\sum_{i<j}W_{ij}x_{i}x_{j}+\frac{\lambda}{N}\sum_{i<j}x_{i}x_{i}^{*}x_{j}x_{j}^{*}.$$

From the formulas (3) and (4), it is straightforward to see that

$$F_{N}=\frac{1}{N}\operatorname{\mathbb{E}}\log~{}\int e^{-H(\bm{x})}\mathrm{d}P_{\textup{{x}}}^{\otimes N}(\bm{x}),$$

This provides another way of interpreting $F_{N}$ as the expected log-partition function (or normalizing constant) of the posterior $\operatorname{\mathbb{P}}_{\lambda}(\cdot|\bm{Y})$. For an integer $n\geq 1$ and $f:(\mathbb{R}^{N})^{n+1}\mapsto\mathbb{R}$, we define the Gibbs average of $f$ w.r.t. $H$ as

$$\left\langle f(\bm{x}^{(1)},\cdots,\bm{x}^{(n)},\bm{x}^{*})\right\rangle:=\frac{\int f(\bm{x}^{(1)},\cdots,\bm{x}^{(n)},\bm{x}^{*})\prod_{l=1}^{n}e^{-H(\bm{x}^{(l)})}\mathrm{d}P_{\textup{{x}}}^{\otimes N}(\bm{x}^{(l)})}{\int\prod_{l=1}^{n}e^{-H(\bm{x}^{(l)})}\mathrm{d}P_{\textup{{x}}}^{\otimes N}(\bm{x}^{(l)})}.$$ (21)

This is nothing else that the average of $f$ with respect to $\operatorname{\mathbb{P}}_{\lambda}(\cdot|\bm{Y})^{\otimes n}$. The variables $\bm{x}^{(l)},l=1\cdots,n$ are called replicas, and are interpreted as random variables independently drawn from the posterior. When $n=1$ we simply write $f(\bm{x},\bm{x}^{*})$ instead of $f(\bm{x}^{(1)},\bm{x}^{*})$. Throughout the rest of the manuscript, we use the following notation: for $l,l^{\prime}=1,\cdots,n,*$, we let

$$R_{l,l^{\prime}}:=\bm{x}^{(l)}\cdot\bm{x}^{(l^{\prime})}=\frac{1}{N}\sum_{i=1}^{N}x_{i}^{(l)}x_{i}^{(l^{\prime})}.$$

In this section we show the convergence of the first 4 moments of the overlap at optimal rates under some conditions: if either the prior $P_{\textup{{x}}}$ is not symmetric about the origin or the Hamiltonian $H$ is “perturbed” in the following sense. Let $t\in[0,1]$ and consider the“ interpolating” Hamiltonian (this qualification will become clear in the next section)

$$-H_{t}(\bm{x}) :=-\frac{t\lambda}{2N}\sum_{i<j}x_{i}^{2}x_{j}^{2}+\sqrt{\frac{t\lambda}{N}}\sum_{i<j}W_{ij}x_{i}x_{j}+\frac{t\lambda}{N}\sum_{i<j}x_{i}x_{i}^{*}x_{j}x_{j}^{*}$$ (22)

$$~{}~{}~{}-\frac{(1-t)r}{2}\sum_{i=1}^{N}x_{i}^{2}+\sqrt{(1-t)r}\sum_{i=1}^{N}z_{i}x_{i}+(1-t)r\sum_{i=1}^{N}x_{i}x_{i}^{*},$$

where the $z_{i}$’s are i.i.d. standard Gaussian r.v.’s independent of everything else, and $r=\lambda q^{*}(\lambda)$. We similarly define the Gibbs average $\langle\cdot\rangle_{t}$ as in (21) where $H$ is replaced by $H_{t}$. We now state a fundamental property satisfied by both $\langle\cdot\rangle$ and $\langle\cdot\rangle_{t}$.

The Nishimori property.

The fact that the Gibbs measure $\langle\cdot\rangle$ is a posterior distribution (19) has far-reaching consequences. A crucial implication is that the $n+1$-tuples $(\bm{x}^{(1)},\cdots,\bm{x}^{(n+1)})$ and $(\bm{x}^{(1)},\cdots,\bm{x}^{(n)},\bm{x}^{*})$ have the same law under $\operatorname{\mathbb{E}}\langle\cdot\rangle$. This fact, which is a simple consequence of Bayes’ rule (see Proposition 16, Lelarge and Miolane, , 2016) prevents replica-symmetry from breaking (see Korada and Macris, , 2009). In particular, $R_{1,2}$ and $R_{1,*}$ have the same distribution. This bares the name of the Nishimori property in the spin glass literature (Nishimori, , 2001). Moreover, this property is preserved under the interpolating Gibbs measure $\langle\cdot\rangle_{t}$ for all $t\in[0,1]$. Indeed, the interpolation is constructed in such a way that $\langle\cdot\rangle_{t}$ is the posterior distribution of the signal $\bm{x}^{*}$ given the augmented set of observations

$$\begin{cases}Y_{ij}&=\sqrt{\frac{t\lambda}{N}}x^{*}_{i}x^{*}_{j}+W_{ij},\quad 1\leq i<j\leq N,\\ y_{i}&=\sqrt{(1-t)r}x^{*}_{i}+z_{i},\quad 1\leq i\leq N,\end{cases}$$ (23)

where one receives side information about $\bm{x}^{*}$ from a scalar Gaussian channel, $r=\lambda q^{*}(\lambda)$, and the signal-to-noise ratios of the two channels are altered in a time dependent way. Now we state our concentration result.

Theorem 7.

For all $\lambda\in\mathcal{A}$ and all $t\in[0,1]$, there exist constants $K(\lambda)\geq 0$ and $c(t)\geq 0$ such that

$$\operatorname{\mathbb{E}}\left\langle\left(R_{1,*}-q^{*}\right)^{4}\right\rangle_{t}\leq K(\lambda)\Big{(}\frac{1}{N^{2}}+e^{-c(t)N}\Big{)}.$$ (24)

Moreover, $c(t)>0$ on $[0,1)$, and if either $\lambda<\lambda_{c}$ or $P_{\textup{{x}}}$ is not symmetric about the origin, then $c(t)\geq c_{0}$ for some constant $c_{0}=c_{0}(\lambda)>0$. Otherwise, $c(t)\sim c_{0}(1-t)^{2}$ as $t\to 1$.

If $P_{\textup{{x}}}$ is symmetric about the origin then the distribution of $R_{1,*}$ under $\operatorname{\mathbb{E}}\langle\cdot\rangle$ is also symmetric, so $\operatorname{\mathbb{E}}\langle R_{1,*}\rangle=0$. If moreover $q^{*}(\lambda)>0$ (i.e., $\lambda>\lambda_{c}$) then (24) becomes trivial at $t=1$ since both sides are constant. On the other hand, if either $t<1$ or $P_{\textup{{x}}}$ is asymmetric, the sign symmetry of the spike is broken. This forces the overlap to be positive and hence concentrate about $q^{*}(\lambda)$. Finally, if $\lambda<\lambda_{c}$, $q^{*}(\lambda)=0$ and the sign symmetry becomes irrelevant since the overlap converges to zero regardless. Let us mention that in the symmetric unperturbed case ($t=1$), we expect a variant of (24) to hold where $R_{1,*}$ is replaced by its absolute value in the statement, and the upper bound would be $K/N^{2}$. Unfortunately, our methods do not allow us to prove such a statement, but we are able to prove a weaker result (see Lemma 13): for all $\epsilon\geq 0$,

$$\operatorname{\mathbb{E}}\big{\langle}\mathds{1}\left\{\big{|}|R_{1,*}|-q^{*}\big{|}\geq\epsilon\right\}\big{\rangle}\longrightarrow 0.$$ (25)

Although this a minor technical point, we also point out that the estimate $c(t)\sim c_{0}(1-t)^{2}$ in the statement is suboptimal. A heuristic argument allows us to get $c(t)\sim c_{0}(1-t)$ as $t\to 1$, but we are currently unable to rigorously justify it.

MMSE.

The bound (24) can be used to deduce the optimal error of estimating $\bm{x}^{*}$ based on the observations (23). The posterior mean $\langle\bm{x}\rangle_{t}$ is the estimator with Minimal Mean Squared Error (MMSE) among all estimators $\widehat{\theta}(\bm{Y},\bm{y})\in\mathbb{R}^{N}$, and the MMSE is

$$\frac{1}{N}\sum_{i=1}^{N}\operatorname{\mathbb{E}}\left[(x^{*}_{i}-\langle x_{i}\rangle_{t})^{2}\right] =\operatorname{\mathbb{E}}_{P_{\textup{{x}}}}[X^{2}]-\frac{2}{N}\sum_{i=1}^{N}\operatorname{\mathbb{E}}\langle x_{i}x_{i}^{*}\rangle_{t}+\frac{1}{N}\sum_{i=1}^{N}\operatorname{\mathbb{E}}\langle x_{i}\rangle_{t}^{2}$$

$$=\operatorname{\mathbb{E}}_{P_{\textup{{x}}}}[X^{2}]-\operatorname{\mathbb{E}}\langle R_{1,*}\rangle_{t}.$$

The last line follows from the Nishimori property, since $\operatorname{\mathbb{E}}\langle x\rangle_{t}^{2}=\operatorname{\mathbb{E}}\langle x^{(1)}x^{(2)}\rangle_{t}=\operatorname{\mathbb{E}}\langle xx^{*}\rangle_{t}$. Theorem 7 implies in particular (under the conditions of its validity) that $\operatorname{\mathbb{E}}\langle R_{1,*}\rangle_{t}\to q^{*}(\lambda)$, yielding the value of the MMSE. It is in particular possible to estimate the spike $\bm{x}^{*}$ from the observations (23) with non-trivial accuracy if and only if $\lambda>\lambda_{c}$. Note that at $t=1$ (no side information) the result still holds below $\lambda_{c}$ or when the prior is not symmetric. Otherwise, as mentioned before, the problem is invariant under a sign flip of $\bm{x}^{*}$ so one has to change the measure of performance. Beside the result (25), we are unable to say much in this situation.

Asymptotic variance.

By Jensen’s inequality we deduce from (24) the convergence of the second moment:

$$\operatorname{\mathbb{E}}\left\langle\left(R_{1,*}-q^{*}\right)^{2}\right\rangle_{t}\leq K(\lambda)\Big{(}\frac{1}{N}+e^{-c(t)N}\Big{)}.$$ (26)

To establish our finite-size correction result (Theorem 2) we need to prove a result stronger than (26), namely that $N\cdot\operatorname{\mathbb{E}}\left\langle\left(R_{1,*}-q^{*}\right)^{2}\right\rangle_{t}$ converges to a limit. For $t\in[0,1]$ and $\lambda\in\mathcal{A}$, we let

$$\Delta_{\mathsf{RS}}(\lambda;t):=\frac{1}{\lambda}\left(-\frac{\mu_{1}}{1-t\mu_{1}}+\frac{2\mu_{2}}{1-t\mu_{2}}+\lambda\frac{4a(1)-3a(2)}{(1-t\mu_{1})^{2}}\right),$$ (27)

where $\mu_{1}$ and $\mu_{2}$ are defined in (12).

Theorem 8.

For all $\lambda\in\mathcal{A}$ and all $t\in[0,1]$, there exist constants $K(\lambda)\geq 0$ and $c(t)\geq 0$ such that

$$\left|N\cdot\operatorname{\mathbb{E}}\left\langle\left(R_{1,*}-q^{*}\right)^{2}\right\rangle_{t}-\Delta_{\mathsf{RS}}(\lambda;t)\right|\leq K(\lambda)\left(\frac{1}{\sqrt{N}}+Ne^{-c(t)N}\right).$$

Moreover, $c(t)>0$ on $[0,1)$, and if either $\lambda<\lambda_{c}$ or $P_{\textup{{x}}}$ is not symmetric about the origin, then $c(t)\geq c_{0}$ for some constant $c_{0}=c_{0}(\lambda)>0$. Otherwise, $c(t)\sim c_{0}(1-t)^{2}$ as $t\to 1$.

The proofs of Theorems 7 and 8 rely on the cavity method, and will be presented in Section 5. Finally, the techniques we use could be easily extended to prove convergence of all the moments at optimal rates: for all integers $k$,

$$\operatorname{\mathbb{E}}\left\langle\left(R_{1,*}-q^{*}\right)^{2k}\right\rangle_{t}\leq\frac{K(k)}{N^{k}}+K(k)e^{-c(k,t)N},$$

but we will not need this stronger statement.

4 The interpolation method

In this section we present the interpolation method of Guerra, (2001). All our main arguments will rely, in one way or another, on this method. Along the way, we prove Theorem 2. The idea is to construct a continuous interpolation path between the Hamiltonian $H$ and a simpler Hamiltonian that decouples all the variables, and analyze the incremental change in the free energy along the path. We present two versions of this method. The first one is the classical method which is applied to the free energy of the entire system, and a second one applied to the free energy of a more restricted system.

4.1 The Guerra interpolation

Our interpolating Hamiltonian is $H_{t}$ from (22) with $r=\lambda q$ for some $q\geq 0$. Now we consider the interpolating free energy

$$\varphi(t):=\frac{1}{N}\operatorname{\mathbb{E}}\log\int e^{-H_{t}(\bm{x})}\mathrm{d}P_{\textup{{x}}}^{\otimes N}(\bm{x}).$$ (28)

We see that $\varphi(1)=F_{N}$ and $\varphi(0)=\psi(\lambda q)$. This function is moreover differentiable in $t$, and by differentiation, we have

$$\varphi^{\prime}(t) =\frac{1}{N}\operatorname{\mathbb{E}}\left\langle-\frac{\mathrm{d}H_{t}(\bm{x})}{\mathrm{d}t}\right\rangle_{t}$$

$$=\frac{1}{N}\operatorname{\mathbb{E}}\left\langle-\frac{\lambda}{2N}\sum_{i<j}x_{i}^{2}x_{j}^{2}+\frac{1}{2}\sqrt{\frac{\lambda}{tN}}\sum_{i<j}W_{ij}x_{i}x_{j}+\frac{\lambda}{N}\sum_{i<j}x_{i}x_{i}^{*}x_{j}x_{j}^{*}\right\rangle_{t}$$

$$~{}~{}~{}+\frac{1}{N}\operatorname{\mathbb{E}}\left\langle\frac{\lambda q}{2}\sum_{i=1}^{N}x_{i}^{2}-\frac{1}{2}\sqrt{\frac{\lambda q}{1-t}}\sum_{i=1}^{N}z_{i}x_{i}-\lambda q\sum_{i=1}^{N}x_{i}x_{i}^{*}\right\rangle_{t}.$$

Now we use Gaussian integration by parts to eliminate the variables $W_{ij}$ and $z_{i}$. The details of this computation are explained extensively in many sources. See (Talagrand, 2011a, ; Krzakala et al., , 2016; Lelarge and Miolane, , 2016). We get

$$\varphi^{\prime}(t) =-\frac{\lambda}{2N^{2}}\operatorname{\mathbb{E}}\left\langle\sum_{i<j}x_{i}^{(1)}x_{j}^{(1)}x_{i}^{(2)}x_{j}^{(2)}\right\rangle_{t}+\frac{\lambda}{N^{2}}\operatorname{\mathbb{E}}\left\langle\sum_{i<j}x_{i}x_{i}^{*}x_{j}x_{j}^{*}\right\rangle_{t}$$

$$~{}~{}~{}+\frac{\lambda q}{2N}\operatorname{\mathbb{E}}\left\langle\sum_{i=1}^{N}x_{i}^{(1)}x_{i}^{(2)}\right\rangle_{t}-\frac{\lambda q}{N}\operatorname{\mathbb{E}}\left\langle\sum_{i=1}^{N}x_{i}x_{i}^{*}\right\rangle_{t}.$$

Completing the squares yields

$$\varphi^{\prime}(t) =-\frac{\lambda}{4}\operatorname{\mathbb{E}}\left\langle(\bm{x}^{(1)}\cdot\bm{x}^{(2)}-q)^{2}\right\rangle_{t}+\frac{\lambda}{4}q^{2}+\frac{\lambda}{4N^{2}}\sum_{i=1}^{N}\operatorname{\mathbb{E}}\left\langle{x_{i}^{(1)}}^{2}{x_{i}^{(2)}}^{2}\right\rangle_{t}$$ (29)

$$~{}~{}~{}+\frac{\lambda}{2}\operatorname{\mathbb{E}}\left\langle(\bm{x}\cdot\bm{x}^{*}-q)^{2}\right\rangle_{t}-\frac{\lambda}{2}q^{2}-\frac{\lambda}{2N^{2}}\sum_{i=1}^{N}\operatorname{\mathbb{E}}\left\langle{x_{i}}^{2}{x_{i}^{*}}^{2}\right\rangle_{t}.$$

The first line in the above expression involves overlaps between two independent replicas, while the second one involves overlaps between one replica and the planted solution. Using the Nishimori property, the derivative of $\varphi$ can be written as

$$\varphi^{\prime}(t)=\frac{\lambda}{4}\operatorname{\mathbb{E}}\left\langle(R_{1,*}-q)^{2}\right\rangle_{t}-\frac{\lambda}{4}q^{2}-\frac{\lambda}{4N}\operatorname{\mathbb{E}}\left\langle{x_{N}}^{2}{x_{N}^{*}}^{2}\right\rangle_{t}.$$ (30)

The last term follows by symmetry between sites. Now, integrating over $t$, the difference between the free energy and the $\mathsf{RS}$ potential $F(\lambda,q)$ can be written in the form of a sum rule:

$$F_{N}-F(\lambda,q)=\frac{\lambda}{4}\int_{0}^{1}\Big{(}\operatorname{\mathbb{E}}\left\langle(R_{1,*}-q)^{2}\right\rangle_{t}-\frac{1}{N}\operatorname{\mathbb{E}}\left\langle{x_{N}}^{2}{x_{N}^{*}}^{2}\right\rangle_{t}\Big{)}\mathrm{d}t.$$ (31)

We see from (31) that $F_{N}$ converges to $F(\lambda,q)$ if and only if the overlap $R_{1,*}$ concentrates about $q$. This happens only for a value of $q$ that maximizes the $\mathsf{RS}$ potential $F(\lambda,\cdot)$. Using Theorem 7 one can already prove the $1/N$ optimal rate below $\lambda_{c}$ or above it when the prior is not symmetric. Indeed since $c(t)$ is lower-bounded by a positive constant in this case, the bound (26) yields $\int_{0}^{1}\operatorname{\mathbb{E}}\langle(R_{1,*}-q^{*})^{2}\rangle_{t}\mathrm{d}t\leq K(\lambda)/N$. Also, the second integrand in (31) is bounded by $K/N$ for some constant $K\geq 0$, so we have for all $\lambda\in\mathcal{A}$, $F_{N}=\phi_{\mathsf{RS}}(\lambda)+\mathcal{O}(1/N)$. If $\lambda>\lambda_{c}$ and the prior is symmetric then we are only able to prove a rate of $1/\sqrt{N}$ due to the fact $c(t)\sim c_{0}(1-t)^{2}$ as $t\to 1$. The $1/N$ rate would follow immediately in this case if one is able to improve the latter estimate to $c(t)\sim c_{0}(1-t)$. To go further, we use Theorem 8, and the additional fact that $\operatorname{\mathbb{E}}\langle{x_{N}}^{2}{x_{N}^{*}}^{2}\rangle_{t}$ has a limit:

Lemma 9.

For all $\lambda\in\mathcal{A}$ and for all $t\in[0,1)$, there exist constants $K(\lambda)\geq 0$ and $c(t)\geq 0$ such that

$$\left|\operatorname{\mathbb{E}}\left\langle{x_{N}}^{2}{x_{N}^{*}}^{2}\right\rangle_{t}-a(0)\right|\leq K(\lambda)\left(\frac{1}{\sqrt{N}}+e^{-c(t)N}\right).$$

Moreover, $c(t)>0$ on $[0,1)$, and if either $\lambda<\lambda_{c}$ or $P_{\textup{{x}}}$ is not symmetric about the origin, then $c(t)\geq c_{0}$ for some constant $c_{0}=c_{0}(\lambda)>0$. Otherwise, $c(t)\sim c_{0}(1-t)^{2}$ as $t\to 1$.

The proof of Lemma 9 relies on the cavity method, and will be presented in the Section 5. Now we are ready to prove Theorem 2.

Proof of Theorem 2. By formula (31) with the choice $q=q^{*}(\lambda)$, we have

$$\left|N(F_{N}-\phi_{\mathsf{RS}}(\lambda))-\frac{\lambda}{4}\Big{(}\int_{0}^{1}\Delta_{\mathsf{RS}}(\lambda;t)\mathrm{d}t-a(0)\Big{)}\right| \leq\frac{\lambda}{4}\int_{0}^{1}\left|N\operatorname{\mathbb{E}}\left\langle\left(R_{1,*}-q^{*}\right)^{2}\right\rangle_{t}-\Delta_{\mathsf{RS}}(\lambda;t)\right|\mathrm{d}t$$

$$~{}+\frac{\lambda}{4}\int_{0}^{1}\left|\operatorname{\mathbb{E}}\left\langle{x_{N}}^{2}{x_{N}^{*}}^{2}\right\rangle_{t}-a(0)\right|\mathrm{d}t.$$

By Theorem 8 and Lemma 9, the integrands on the right-hand side are bounded by $K/\sqrt{N}+KNe^{-c(t)N}$ where $c(t)>c_{0}>0$ for all $t$ in the cases $\lambda<\lambda_{c}$ or $P_{\textup{{x}}}$ not symmetric about the origin, so the convergence follows. The function $\psi_{\mathsf{RS}}(\lambda)$ is the second term in the left-hand side. Formula (13) follows by integration.  

4.2 The main estimate: energy gap at suboptimal overlap

Recall the interpolating Hamiltonian $H_{t}$ from (22) with $r=\lambda q^{*}(\lambda)$. Let us now introduce the Franz-Parisi potential (Franz and Parisi, , 1995). For $m\in\mathbb{R}$ and $\epsilon>0$ we define

$$\Phi_{\epsilon}(m;t):=\frac{1}{N}\operatorname{\mathbb{E}}\log\int\mathds{1}\{R_{1,*}\in[m,m+\epsilon)\}e^{-H_{t}(\bm{x})}\mathrm{d}P_{\textup{{x}}}^{\otimes N}(\bm{x}).$$ (32)

This is the free energy of a subsystem of configurations having an overlap close to a fixed value $m$ with the planted signal $\bm{x}^{*}$. It is clear that $\Phi_{\epsilon}(m;t)\leq\varphi(t)$, where the latter is the interpolating free energy defined in (28). The purpose of this section is to prove that when $m$ is far from $q^{*}(\lambda)$ then there is a sizable gap between $\Phi_{\epsilon}(m;t)$ and $\varphi(t)$. This estimate is a main ingredient is our proof of overlap concentration. (The other main ingredient is the cavity method, which will be presented in the next section.) To prove this we will need the auxiliary function

$$\phi_{\mathsf{RS}}(\lambda;t)=\sup_{q\geq 0}~{}\psi(\lambda q)-\frac{t\lambda q^{2}}{4}.$$

One can show that the above formula is the limit of $\varphi(t)$ as $N\to\infty$, for example, by using the so called “Aizenman-Sims-Starr scheme” (Aizenman et al., , 2003); see (Lelarge and Miolane, , 2016). For our purposes we will only need the inequality

$$\varphi(t)\geq\phi_{\mathsf{RS}}(\lambda;t)-\frac{K\lambda t}{N},$$ (33)

which can be proved using the interpolation method presented in the previous section and dropping the non-negative term $\operatorname{\mathbb{E}}\langle(R_{1,*}-q^{*})^{2}\rangle$ from the expression analogous to (30) in this case. Now it suffices to compare $\Phi_{\epsilon}(m;t)$ to $\phi_{\mathsf{RS}}(\lambda;t)$. The result is given in Proposition 12, and we finish this subsection by Proposition 13 showing convergence in probability of the overlaps as a straightforward consequence.

For $r\geq 0$ and $s\in\mathbb{R}$, we let

$$\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{3.65486pt}{0.43057pt}}{\psi}(r,s):=\operatorname{\mathbb{E}}_{x^{*},z}\log\int\exp\left(\sqrt{r}zx+sxx^{*}-\frac{r}{2}x^{2}\right)\mathrm{d}P_{\textup{{x}}}(x).$$ (34)

We see that $\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{3.65486pt}{0.43057pt}}{\psi}(r,r)=\psi(r)$, but unlike $\psi$, the function $\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{3.65486pt}{0.43057pt}}{\psi}$ does not have an interpretation as the $\mathsf{KL}$ between two distributions. The next lemma states some key properties of this function that will be useful later on.

Lemma 10.

For all $r\geq 0$, it holds that

• The function $s\mapsto\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{3.65486pt}{0.43057pt}}{\psi}(r,s)$ is strictly convex, hence strongly convex on any compact.

• There exist a constant $c=c(r,P_{\textup{{x}}})\geq 0$ such that $\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{3.65486pt}{0.43057pt}}{\psi}(r,-r)\leq\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{3.65486pt}{0.43057pt}}{\psi}(r,r)-c$. If $r>0$ then $c>0$ unless the prior $P_{\textup{{x}}}$ is symmetric about the origin (in which case $\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{3.65486pt}{0.43057pt}}{\psi}(r,-r)=\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{3.65486pt}{0.43057pt}}{\psi}(r,r)$).

• The map $r\mapsto c(r,P_{\textup{{x}}})$ is increasing on $\mathbb{R}_{+}$.

The proof of the above lemma can be found in the Appendix. We now state a useful interpolation bound on $\Phi_{\epsilon}(m;t)$. This is a simpler version of the Guerra-Talagrand $\mathsf{1RSB}$ interpolation bound at fixed overlap, a key invention that ultimately paved the way towards a proof of the Parisi formula (Guerra, , 2003; Talagrand, , 2006). In some sense, since we are dealing with a planted model, we only need a replica-symmetric version of this bound.

Proposition 11.

Fix $m\in\mathbb{R}$, $\epsilon>0$, $t\in[0,1]$ and $\lambda\geq 0$. Let $r=(1-t)\lambda q^{*}+t\lambda|m|$, $\bar{r}=(1-t)\lambda q^{*}+t\lambda m$. There exist constants $K=K(P_{\textup{{x}}})>0$, $K^{\prime}=K^{\prime}(\lambda)>0$ such that

$$\Phi_{\epsilon}(m;t) \leq\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{3.65486pt}{0.43057pt}}{\psi}\big{(}r,\bar{r}\big{)}-\frac{t\lambda m^{2}}{4}-K\left(m-\partial_{s}\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{3.65486pt}{0.43057pt}}{\psi}\big{(}r,\bar{r}\big{)}\right)^{2}+K^{\prime}\epsilon^{2}+\frac{K^{\prime}}{N}.$$

Proof.

To obtain a bound on $\Phi_{\epsilon}(m;t)$ for any fixed $t$, we use the interpolation method with Hamiltonian

$$-H_{t,s}(\bm{x}) :=\sum_{i<j}-\frac{ts\lambda}{2N}x_{i}^{2}x_{j}^{2}+\sqrt{\frac{ts\lambda}{N}}W_{ij}x_{i}x_{j}+\frac{ts\lambda}{N}x_{i}x_{i}^{*}x_{j}x_{j}^{*}$$

$$~{}+\sum_{i=1}^{N}-\frac{(1-t)\lambda q^{*}}{2}x_{i}^{2}+\sqrt{(1-t)\lambda q^{*}}z_{i}x_{i}+(1-t)\lambda q^{*}x_{i}x_{i}^{*}$$

$$~{}+\sum_{i=1}^{N}-\frac{(1-s)t\lambda|m|}{2}x_{i}^{2}+\sqrt{(1-s)t\lambda|m|}z_{i}^{\prime}x_{i}+(1-s)t\lambda mx_{i}x_{i}^{*},$$

by varying $s\in[0,1]$. The r.v.’s $W,z,z^{\prime}$ are all i.i.d. standard Gaussians independent of everything else. We define

$$\varphi(t,s):=\frac{1}{N}\operatorname{\mathbb{E}}\log\int\mathds{1}\{R_{1,*}\in[m,m+\epsilon)\}e^{-H_{t,s}(\bm{x})}\mathrm{d}P_{\textup{{x}}}^{\otimes N}(\bm{x}).$$

We compute the derivative w.r.t. $s$. The same algebraic manipulations conducted in the computation of $\varphi^{\prime}$ up to (29) apply here, and we get

$$\partial_{s}\varphi(t,s)= -\frac{\lambda t}{4}\operatorname{\mathbb{E}}\left\langle(\bm{x}^{(1)}\cdot\bm{x}^{(2)}-|m|)^{2}\right\rangle_{t,s}+\frac{\lambda t}{4}|m|^{2}+\frac{\lambda t}{4N^{2}}\sum_{i=1}^{N}\operatorname{\mathbb{E}}\left\langle{x_{i}^{(1)}}^{2}{x_{i}^{(2)}}^{2}\right\rangle_{t,s}$$

$$~{}~{}~{}+\frac{\lambda t}{2}\operatorname{\mathbb{E}}\left\langle(\bm{x}\cdot\bm{x}^{*}-m)^{2}\right\rangle_{t,s}-\frac{\lambda t}{2}m^{2}-\frac{\lambda t}{2N^{2}}\sum_{i=1}^{N}\operatorname{\mathbb{E}}\left\langle{x_{i}}^{2}{x_{i}^{*}}^{2}\right\rangle_{t,s},$$

where $\langle\cdot\rangle_{t,s}$ is the Gibbs average w.r.t. the Hamiltonian $-H_{t,s}(\bm{x})+\log\mathds{1}\{\bm{x}\cdot\bm{x}^{*}\in[m,m+\epsilon)\}$. A few things now happen. Notice that the planted term (first term in the second line) is trivially smaller than $t\lambda\epsilon^{2}/2$ due to the overlap restriction. Moreover, the last terms in both lines are of order $1/N$ since the variables $x_{i}$ are bounded. The first term in the first line, which involves the overlap between two replicas, is more challenging. What makes this term difficult to control is that the Gibbs measure $\langle\cdot\rangle_{t,s}$ no longer satisfies the Nishimori property due to the overlap restriction, so the overlap between two replicas no longer has the same distribution as the overlap of one replica with the planted spike. Fortunately, this term is always non-positive so we can ignore it altogether and obtain an upper bound:

$$\partial_{s}\varphi(t,s)\leq-\frac{\lambda t}{4}m^{2}+\frac{\lambda t\epsilon^{2}}{2}+\frac{\lambda K}{N}.$$

Integrating over $s$, we get

$$\Phi_{\epsilon}(m;t)\leq\varphi(t,0)-\frac{\lambda t}{4}m^{2}+\frac{\lambda t\epsilon^{2}}{2}+\frac{\lambda K}{N}.$$

Now it remains to show that

$$\varphi(t,0)\leq\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{3.65486pt}{0.43057pt}}{\psi}(r,\bar{r})-K\left(m-\partial_{s}\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{3.65486pt}{0.43057pt}}{\psi}(r,\bar{r})\right)^{2}+\mathcal{O}(\epsilon^{2}).$$

By properties of the Gaussian distribution, we can write $-H_{t,0}=\sum_{i=1}^{N}\sqrt{r}z_{i}x_{i}+\bar{r}x_{i}x_{i}^{*}-\frac{r}{2}x_{i}^{2}$. Define the following (random) probability measure

$$G(A):=\frac{\int_{A}e^{-H_{t,0}(\bm{x})}\mathrm{d}P_{\textup{{x}}}^{\otimes N}(\bm{x})}{\int e^{-H_{t,0}(\bm{x})}\mathrm{d}P_{\textup{{x}}}^{\otimes N}(\bm{x})},$$

for all Borel sets $A\subseteq\mathbb{R}^{N}$. We observe that conditionally on the Gaussian vector $\bm{z}$ and the planted vector $\bm{x^{*}}$, $G$ is a product measure due to the additive form of $H_{t,0}$. Moreover,

$$\varphi(t;0)-\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{3.65486pt}{0.43057pt}}{\psi}(r,\bar{r})=\frac{1}{N}\operatorname{\mathbb{E}}\log G(\{R_{1,*}\in[m,m+\epsilon)\}),$$

so will be interested in a large deviation bound on the above quantity. The prior $P_{\textup{{x}}}$ is of bounded support, thus the marginals of $G$ (conditional on $\bm{x}^{*}$ and $\bm{z}$) are clearly sub-Gaussian. Therefore, by concentration of measure, the empirical average $\bm{x}\cdot\bm{x}^{*}/N$ must concentrate around its expectation: for all $u\geq 0$

$$G\left(\left\{\frac{1}{N}\sum_{i=1}^{N}(x_{i}-\operatorname{\mathbb{E}}_{G}[x_{i}])x^{*}_{i}\geq u\right\}\right)\leq e^{-Nu^{2}/2K^{2}},$$

where $K$ is for instance twice the diameter of the support of $P_{\textup{{x}}}$. This implies

$$\frac{1}{N}\log G(\{R_{1,*}\in[m,m+\epsilon)\})\leq-\frac{(m-\widehat{q})^{2}}{2K^{2}}\mathds{1}\{\widehat{q}\leq m\}-\frac{(m+\epsilon-\widehat{q})^{2}}{2K^{2}}\mathds{1}\{\widehat{q}\geq m+\epsilon\},$$

where $\widehat{q}=\frac{1}{N}\sum_{i=1}^{N}\operatorname{\mathbb{E}}_{G}[x_{i}]x^{*}_{i}$. Now by Jensen’s inequality ($x\mapsto(x-a)^{2}\mathds{1}\{x\leq a\}$ and $x\mapsto(x-b)^{2}\mathds{1}\{x\geq b\}$ are convex), we can write

$$\frac{1}{N}\operatorname{\mathbb{E}}\log G(\{R_{1,*}\in[m,m+\epsilon)\}) \leq-\frac{(m-\operatorname{\mathbb{E}}[\widehat{q}])^{2}}{2K^{2}}\mathds{1}\left\{\operatorname{\mathbb{E}}[\widehat{q}]\leq m\right\}$$

$$~{}~{}-\frac{(m+\epsilon-\operatorname{\mathbb{E}}[\widehat{q}])^{2}}{2K^{2}}\mathds{1}\left\{\operatorname{\mathbb{E}}[\widehat{q}]\geq m+\epsilon\right\}.$$

Since

$$\operatorname{\mathbb{E}}_{G}[x_{i}]=\frac{\int xe^{\sqrt{r}z_{i}x+\bar{r}xx_{i}^{*}-\frac{r}{2}x^{2}}\mathrm{d}P_{\textup{{x}}}(x)}{\int e^{\sqrt{r}z_{i}x+\bar{r}xx_{i}^{*}-\frac{r}{2}x^{2}}\mathrm{d}P_{\textup{{x}}}(x)},$$

we have $\operatorname{\mathbb{E}}[\widehat{q}]=\partial_{s}\psi(r,\bar{r})$. We now use the elementary inequality $\frac{1}{2}(x-a)^{2}-(a-b)^{2}\leq(x-a)^{2}\mathds{1}\{x\leq a\}+(x-b)^{2}\mathds{1}\{x\geq b\}$, valid for all $x\in\mathbb{R}$ and $a\leq b$, to simplify the above bound and obtain

$$\frac{1}{N}\operatorname{\mathbb{E}}\log G(\{R_{1,*}\in[m,m+\epsilon)\})\leq-\frac{(m-\partial_{s}\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{3.65486pt}{0.43057pt}}{\psi}(r,\bar{r}))^{2}}{4K^{2}}+\frac{\epsilon^{2}}{2K^{2}}.$$

This allows us to conclude. $\blacksquare$

A consequence of the above proposition is an energy gap property: if $m$ is far from $q^{*}(\lambda)$ then the free energy $\Phi_{\epsilon}(m;t)$ of the configurations having overlap $m$ with $\bm{x}^{*}$ is strictly smaller than $\phi_{\mathsf{RS}}(\lambda;t)$:

Proposition 12.

For all $\lambda\in\mathcal{A}$, all $\epsilon>0$ and all $t\in[0,1]$, there exist constants $c=c(\lambda,\epsilon,t,P_{\textup{{x}}})\geq 0$ and $\epsilon^{\prime}=\epsilon^{\prime}(\lambda,\epsilon)>0$ such that

$$\forall m\in\mathbb{R}\qquad|m-q^{*}(\lambda)|\geq\epsilon\qquad\implies\qquad\Phi_{\epsilon^{\prime}}(m;t)\leq\phi_{\mathsf{RS}}(\lambda;t)-c.$$

Moreover, if $t<1$ then $c>0$. If either $\lambda<\lambda_{c}$ or $P_{\textup{{x}}}$ is not symmetric about the origin $\inf_{t\in[0,1]}c(t)>0$. Lastly, if $\lambda>\lambda_{c}$ and $P_{\textup{{x}}}$ is symmetric, then $c(t)\sim c_{0}(1-t)$ as $t\to 1$, for some $c_{0}=c_{0}(\lambda,\epsilon,P_{\textup{{x}}})>0$.

A direct consequence of the above energy gap result is the convergence in probability of the overlaps:

Proposition 13.

For all $\lambda\in\mathcal{A}$, all $\epsilon>0$ and all $t\in[0,1]$, there exist constants $K=K(\lambda,\epsilon)\geq 0,~{}c=c(\lambda,\epsilon,t,P_{\textup{{x}}})\geq 0$ such that

$$\operatorname{\mathbb{E}}\left\langle\mathds{1}\left\{\big{|}R_{1,*}-q^{*}(\lambda)\big{|}\geq\epsilon\right\}\right\rangle_{t}\leq Ke^{-cN},$$

where the constant $c$ the same properties as in Proposition 12, except that $c(t)\sim c_{0}(1-t)^{2}$ as $t\to 1$. Moreover, if $\lambda>\lambda_{c}$, $P_{\textup{{x}}}$ is symmetric and $t=1$ then one still has

$$\operatorname{\mathbb{E}}\left\langle\mathds{1}\left\{\big{|}|R_{1,*}|-q^{*}(\lambda)\big{|}\geq\epsilon\right\}\right\rangle_{t}\leq Ke^{-cN},$$

with $c=c(\lambda,\epsilon,P_{\textup{{x}}})>0$.

To prove the above lemma, we first show that the partition function of the model enjoys sub-Gaussian concentration in logarithmic scale. This is an elementary consequence of two classical concentration-of-measure results: concentration of Lipschitz functions of Gaussian random variables, and concentration of convex Lipschitz function of bounded random variables. See Boucheron et al., (2013) and van Handel, (2014).

Lemma 14.

Let $A$ be a Borel subset of $\mathbb{R}^{N}$, and define the random variable

$$Z:=\int_{A}e^{-H_{t}(\bm{x})}\mathrm{d}P_{\textup{{x}}}^{\otimes N}(\bm{x}).$$

There exist a constant $K>0$ depending only on $\lambda$ and $P_{\textup{{x}}}$ such that for all $u\geq 0$,

$$\Pr\left(\left|\frac{1}{N}\log Z-\frac{1}{N}\operatorname{\mathbb{E}}\log Z\right|\geq u\right)\leq 4e^{-Nu^{2}/K}.$$

Proof of Lemma 14. It suffices to notice that the map $(\bm{W},\bm{z})\mapsto\frac{1}{N}\log Z(\bm{W},\bm{z})$ is Lipschitz with constant $K\sqrt{\frac{\lambda}{N}}$ for every $\bm{x}^{*}\in\mathbb{R}^{N}$, and that the map $\bm{x}^{*}\mapsto\frac{1}{N}\operatorname{\mathbb{E}}[\log Z|\bm{x^{*}}]$ (where the expectation is over $\bm{W},\bm{z}$) is convex and Lipschitz with constant $K\frac{\lambda}{\sqrt{N}}$. Then we use concentration of Lipschitz functions of Gaussian r.v.’s and of convex Lipschitz functions of bounded r.v.’s (since the coordinates $x^{*}_{i}$ are bounded).  

Proof of Proposition 13. For $\epsilon,\epsilon^{\prime}>0,~{}t\in[0,1)$, we can write the decomposition

$$\operatorname{\mathbb{E}}\left\langle\mathds{1}\left\{|R_{1,*}-q^{*}(\lambda)|\geq\epsilon\right\}\right\rangle_{t} =\sum_{l\geq 0}\operatorname{\mathbb{E}}\left\langle\mathds{1}\big{\{}R_{1,*}-q^{*}-\epsilon\in[l\epsilon^{\prime},(l+1)\epsilon^{\prime})\big{\}}\right\rangle_{t}$$

$$~{}+\sum_{l\geq 0}\operatorname{\mathbb{E}}\left\langle\mathds{1}\big{\{}-R_{1,*}+q^{*}-\epsilon\in[l\epsilon^{\prime},(l+1)\epsilon^{\prime})\big{\}}\right\rangle_{t},$$

where the integer index $l$ ranges over a finite set of size $\leq K/\epsilon^{\prime}$ since the prior $P_{\textup{{x}}}$ has bounded support. We will only treat the first sum in the above expression since the argument extends trivially to the second sum. Let $A=\big{\{}R_{1,*}-q^{*}-\epsilon\in[l\epsilon^{\prime},(l+1)\epsilon^{\prime})\big{\}}$ and write

$$\operatorname{\mathbb{E}}\left\langle\mathds{1}(A)\right\rangle_{t}=\operatorname{\mathbb{E}}\left[\frac{\int_{A}e^{-H_{t}(\bm{x})}\mathrm{d}P_{\textup{{x}}}^{\otimes N}(\bm{x})}{\int e^{-H_{t}(\bm{x})}\mathrm{d}P_{\textup{{x}}}^{\otimes N}(\bm{x})}\right].$$ (35)

In virtue of Lemma 14 the two quantities in the above fraction enjoy sub-Gaussian concentration in logarithmic scale. For any given $l$ and $u\geq 0$, we simultaneously have

$$\frac{1}{N}\log\int e^{-H_{t}(\bm{x})}\mathrm{d}P_{\textup{{x}}}^{\otimes N}(\bm{x}) \geq\frac{1}{N}\operatorname{\mathbb{E}}\log\int e^{-H_{t}(\bm{x})}\mathrm{d}P_{\textup{{x}}}^{\otimes N}(\bm{x})-u$$

$$\geq\phi_{\mathsf{RS}}(\lambda;t)-\frac{Kt\lambda}{N}-u,$$

(the last inequality come from (33)), and

$$\frac{1}{N}\log\int_{A}e^{-H_{t}(\bm{x})}\mathrm{d}P_{\textup{{x}}}^{\otimes N}(\bm{x}) \leq\frac{1}{N}\operatorname{\mathbb{E}}\log\int_{A}e^{-H_{t}(\bm{x})}\mathrm{d}P_{\textup{{x}}}^{\otimes N}(\bm{x})+u$$

$$=\Phi_{\epsilon^{\prime}}(q^{*}+\epsilon+l\epsilon^{\prime};t)+u,$$

with probability at least $1-4e^{-Nu^{2}/K}$. On the complement of this event event, we simply bound the fraction in (35) by 1. Combining the above bounds we have

$$\operatorname{\mathbb{E}}\left\langle\mathds{1}(A)\right\rangle_{t}\leq 4e^{-Nu^{2}/K}+e^{N(\delta+2u)},$$

where $\delta=\Phi_{\epsilon^{\prime}}(m;t)-\phi_{\mathsf{RS}}(\lambda;t)+K\lambda t/N$ with $m=q^{*}+\epsilon+l\epsilon^{\prime}$. We let $\epsilon^{\prime}$ be a function of $\lambda$ and $\epsilon$ as dictated by Proposition 12, and $c>0$ such that $\delta\leq-c$ for all $m$ such that $|m-q^{*}|\geq\epsilon$. Now we conclude by letting $u=-\delta/3$. Finally, if $P_{\textup{{x}}}$ is symmetric and $t=1$, then it suffices to consider non-negative values of $m$ in the above argument to prove the corresponding statement.  

Proof of Propopsition 12. The gap we seek to prove will come from different sources, depending on the particular cases we will look at. The treatment will be split into several nested cases, depending on whether $t$ is small or not and whether $m$ positive and negative.

Large $t$.

Assume $t\geq t_{0}$ to be determined later. For $m\geq 0$, Proposition 11 implies

$$\Phi_{\epsilon^{\prime}}(m;t)\leq\psi((1-t)\lambda q^{*}+t\lambda m)-\frac{t\lambda m^{2}}{4}+K^{\prime}\epsilon^{\prime 2}+\frac{K^{\prime}}{N}.$$

Since $\psi$ is a convex function we have

$$\psi((1-t)\lambda q^{*}+t\lambda m)-\frac{t\lambda m^{2}}{4} \leq(1-t)\psi(\lambda q^{*})+t\psi(\lambda m)-\frac{t\lambda m^{2}}{4}$$

$$=(1-t)\psi(\lambda q^{*})+tF(\lambda,m).$$ (36)

Since $q^{*}(\lambda)$ is the unique maximizer of $m\mapsto F(\lambda,m)$, $|m-q^{*}|\geq\epsilon>0$ implies that $F(\lambda,m)\leq F(\lambda,q^{*})-c(\epsilon)$ for some $c(\epsilon)>0$. This in turn implies

$$\Phi_{\epsilon^{\prime}}(m;t) \leq(1-t)\psi(\lambda q^{*})+t\big{(}\psi(\lambda q^{*})-\frac{\lambda q^{*2}}{4}-c(\epsilon)\big{)}+K^{\prime}\epsilon^{\prime 2}+\frac{K^{\prime}}{N}$$

$$=\psi(\lambda q^{*})-\frac{t\lambda q^{*2}}{4}-tc(\epsilon)+K^{\prime}\epsilon^{\prime 2}+\frac{K^{\prime}}{N}$$

$$\leq\phi_{\mathsf{RS}}(\lambda;t)-\frac{t_{0}c(\epsilon)}{2}+\frac{K^{\prime}}{N},$$

where we have chosen $\epsilon^{\prime}$ such that $K^{\prime}\epsilon^{\prime 2}<t_{0}c(\epsilon)/2$. The conclusion is reached for $m\geq 0$. Now we would like to prove the same bound on $\Phi_{\epsilon^{\prime}}$ for negative overlaps. Proposition 11 implies that for $m>0$,

$$\Phi_{\epsilon^{\prime}}(-m;t)\leq\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{3.65486pt}{0.43057pt}}{\psi}((1-t)\lambda q^{*}+t\lambda m,(1-t)\lambda q^{*}-t\lambda m)-\frac{t\lambda m^{2}}{4}+K^{\prime}\epsilon^{\prime 2}+\frac{K^{\prime}}{N}.$$ (37)

If $\lambda<\lambda_{c}$ then $q^{*}(\lambda)=0$, and by Proposition 10 we have $\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{3.65486pt}{0.43057pt}}{\psi}(t\lambda m,-t\lambda m)-\frac{t\lambda m^{2}}{4}\leq\psi(t\lambda m)-\frac{t\lambda m^{2}}{4}\leq t_{0}F(\lambda,m)$, and we finish the argument as in the case of positive overlap. Now we deal with the case $\lambda>\lambda_{c}$.

• Suppose $|m-q^{*}|\geq\epsilon$. We let $r=(1-t)\lambda q^{*}+t\lambda m$ and $\alpha=\frac{(1-t)q^{*}}{(1-t)q^{*}+tm}$.

  $$\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{3.65486pt}{0.43057pt}}{\psi}((1-t)\lambda q^{*}+t\lambda m,(1-t)\lambda q^{*}-t\lambda m) =\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{3.65486pt}{0.43057pt}}{\psi}(r,\alpha r-(1-\alpha)r)$$

  $$\leq\alpha\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{3.65486pt}{0.43057pt}}{\psi}(r,r)+(1-\alpha)\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{3.65486pt}{0.43057pt}}{\psi}(r,-r)$$

  $$\leq\psi(r)$$

  where the last two lines follow from Proposition 10. Since $|m-q^{*}|\geq\epsilon$ we finish once again as in the positive overlap case, starting from line (4.2).

• Suppose $|m-q^{*}|\leq\epsilon$. Then $1-\alpha\geq t_{0}\frac{q^{*}-\epsilon}{q^{*}+\epsilon}$ and $|r-\lambda q^{*}|\leq\lambda\epsilon$. If $P_{\textup{{x}}}$ is asymmetric we use the bounds of Proposition 10:

  $$\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{3.65486pt}{0.43057pt}}{\psi}((1-t)\lambda q^{*}+t\lambda m,(1-t)\lambda q^{*}-t\lambda m) \leq\alpha\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{3.65486pt}{0.43057pt}}{\psi}(r,r)+(1-\alpha)\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{3.65486pt}{0.43057pt}}{\psi}(r,-r)$$

  $$\leq\psi(r)-(1-\alpha)c(r)$$

  $$\leq\psi(r)-t_{0}\frac{q^{*}-\epsilon}{q^{*}+\epsilon}c(\lambda(q^{*}-\epsilon)).$$

  The last line follows since $r\mapsto c(r)$ is increasing. Then we finish the argument by plugging this bound in (37).

Small $t$.

Assume now that $t\leq t_{0}$. In this situation, we draw the gap from the term $(m-\partial_{s}\bar{\psi}(r,\bar{r}))^{2}$ (so far unused) in Proposition 11. The functions $\bar{\psi}(r,\cdot)$ and $\bar{\psi}(\cdot,\cdot)=\psi(\cdot)$ have bounded second derivatives so

$$\max~{}\big{\{}\left|\partial_{s}\bar{\psi}(r,\bar{r})-\partial_{s}\bar{\psi}(r,r)\right|~{}~{},~{}~{}\left|\partial_{s}\bar{\psi}(r,r)-\partial_{s}\bar{\psi}(q^{*},q^{*})\right|\big{\}}~{}~{}\leq K\lambda t_{0}.$$

Moreover,

$$(m-q^{*})^{2}\leq 2(m-\partial_{s}\bar{\psi}(r,\bar{r}))^{2}+2(q^{*}-\partial_{s}\bar{\psi}(r,\bar{r}))^{2}.$$

Since $\partial_{s}\bar{\psi}(q^{*},q^{*})=q^{*}$ we have

$$(m-\partial_{s}\bar{\psi}(r,\bar{r}))^{2}\geq\frac{1}{2}(m-q^{*})^{2}-K\lambda^{2}t_{0}^{2}\geq\frac{\epsilon^{2}}{2}-K\lambda^{2}t_{0}^{2},$$

and here we choose $t_{0}$ to be accordingly small, and we finish the argument.

Note that the assumption that $P_{\textup{{x}}}$ is not symmetric about the origin is used only in the case where the (negative) overlap $-m$ is close to $-q^{*}$. Consequently, the gap is independent of $t$ in all cases. Alternatively, without this asymmetry assumption (and when $q^{*}>0$), we see that there is no hope of a gap independent of $t$ since the potential $\Phi_{\epsilon^{\prime}}(m;t)$ is closer and closer to being even as $t\to 1$. But we can still obtain a gap that depends on $t(1-t)$ via a strong convexity argument.

The $s\mapsto\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{3.65486pt}{0.43057pt}}{\psi}(r,s)$ is strongly convex on any interval, and for all $r\geq 0$. Therefore, recalling $r=(1-t)\lambda q^{*}+t\lambda m$ and $\alpha=\frac{(1-t)q^{*}}{(1-t)q^{*}+tm}$, there exists a constant $c>0$ depending only on $\lambda$ and $P_{\textup{{x}}}$ (this constant is a bound on $r$) such that

$$\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{3.65486pt}{0.43057pt}}{\psi}((1-t)\lambda q^{*}+t\lambda m,(1-t)\lambda q^{*}-t\lambda m) =\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{3.65486pt}{0.43057pt}}{\psi}(r,\alpha r-(1-\alpha)r)$$

$$\leq\alpha\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{3.65486pt}{0.43057pt}}{\psi}(r,r)+(1-\alpha)\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{3.65486pt}{0.43057pt}}{\psi}(r,-r)-\frac{c}{2}\alpha(1-\alpha)(2r)^{2}$$

$$=\alpha\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{3.65486pt}{0.43057pt}}{\psi}(r,r)+(1-\alpha)\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{3.65486pt}{0.43057pt}}{\psi}(r,-r)-2ct(1-t)\lambda^{2}q^{*}m$$

$$\leq\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{3.65486pt}{0.43057pt}}{\psi}(r,r)-2ct(1-t)\lambda^{2}q^{*}(q^{*}-\epsilon),$$

where the last bounds follows from $\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{3.65486pt}{0.43057pt}}{\psi}(r,-r)\leq\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{3.65486pt}{0.43057pt}}{\psi}(r,r)$ and $|m-q^{*}|\leq\epsilon$ (recall that this is the only case where such an argument is needed).  

5 The cavity method

Now that we have established the convergence in probability of $R_{1,*}$ to $q^{*}(\lambda)$ under $\operatorname{\mathbb{E}}\langle\cdot\rangle_{t}$ in Lemma 13, we use the cavity method to prove the convergence of the moments of the overlap. In its essence, the cavity method amounts to isolating one variable from the system and analyzing the influence of the rest of the variables on it. It was initially introduced as an analytic tool, alternative to the replica method, to solve certain models of spin glasses (Mézard et al., , 1990), and has since been tremendously successful in predicting the behavior of many mean-field models. The underlying principle is know as the leave-one-out method in statistics. In our setting, this principle is materialized in the form of an interpolation method (yet again) that separates the last variable from the rest.

Our proofs of Theorems 7 and 8 are interlaced. The skeleton of the argument is as follows:

1. We first prove convergence of the second moment: $\operatorname{\mathbb{E}}\left\langle(R_{1,*}-q^{*})^{2}\right\rangle_{t}\leq\mathcal{O}(1/N+e^{-c(t)N})$.

2. We then deduce from 1. the convergence of the fourth moment via an inductive argument: $\operatorname{\mathbb{E}}\left\langle(R_{1,*}-q^{*})^{4}\right\rangle_{t}\leq\mathcal{O}(1/N^{2}+e^{-c(t)N})$. This finishes the proof of Theorem 7.

3. Using 2., we revisit our proof of 1., and refine the estimates in order to obtain the sharper result $N\cdot\operatorname{\mathbb{E}}\left\langle(R_{1,*}-q^{*})^{2}\right\rangle_{t}\to\Delta_{\mathsf{RS}}(\lambda;t)$. This finishes the proof of Theorem 8.

We will start by defining our interpolating Hamiltonian and state some preliminary bounds and properties. Then we will move on to the execution of the cavity computations.

5.1 Preliminary bounds

In this section the parameter $t\in[0,1]$ is fixed and treated as a constant. We consider the Hamiltonian

$$-H_{t}^{-}(\bm{x}) :=\sum_{i<j\leq N-1}-\frac{\lambda t}{2N}x_{i}^{2}x_{j}^{2}+\sqrt{\frac{\lambda t}{N}}W_{ij}x_{i}x_{j}+\frac{\lambda t}{N}x_{i}x_{i}^{*}x_{j}x_{j}^{*}$$

$$~{}+\sum_{i=1}^{N-1}-\frac{(1-t)r}{2}x_{i}^{2}+\sqrt{(1-t)r}z_{i}x_{i}+(1-t)rx_{i}x_{i}^{*},$$

where we have striped away the contribution of the variable $x_{N}$ from $H_{t}$ (equ. (22)). This contribution is considered separately: for $t^{\prime}\in[0,1]$, we let

$$-h_{t^{\prime}}(\bm{x}) :=\sum_{i=1}^{N-1}-\frac{\lambda t^{\prime}}{2N}x_{i}^{2}x_{N}^{2}+\sqrt{\frac{\lambda t^{\prime}}{N}}W_{iN}x_{i}x_{N}+\frac{\lambda t^{\prime}}{N}x_{i}x_{i}^{*}x_{N}x_{N}^{*}$$

$$~{}~{}~{}-\frac{(1-t^{\prime})r}{2}x_{N}^{2}+\sqrt{(1-t^{\prime})r}z_{N}x_{N}+(1-t^{\prime})rx_{N}x_{N}^{*}.$$

We let $r=\lambda q^{*}(\lambda)$ and let our interpolation, with the time parameter $s\in[0,1]$, be

$$H_{t,s}(\bm{x}):=H_{t}^{-}(\bm{x})+h_{ts}(\bm{x}).$$

At $s=1$ we have $H_{t,s}=H_{t}$, and at $s=0$ the variable $x_{N}$ decouples from the rest of the variables. For an integer $n\geq 1$ and $f:(\mathbb{R}^{N})^{n+1}\mapsto\mathbb{R}$, we define

$$\left\langle f(\bm{x}^{(1)},\cdots,\bm{x}^{(n)},\bm{x}^{*})\right\rangle_{t,s}:=\frac{\int f(\bm{x}^{(1)},\cdots,\bm{x}^{(n)},\bm{x}^{*})\prod_{l=1}^{n}e^{-H_{t,s}(\bm{x}^{(l)})}\mathrm{d}P_{\textup{{x}}}^{\otimes N}(\bm{x}^{(l)})}{\int\prod_{l=1}^{n}e^{-H_{t,s}(\bm{x}^{(l)})}\mathrm{d}P_{\textup{{x}}}^{\otimes N}(\bm{x}^{(l)})},$$

similarly to (21). Following Talagrand’s notation, we write

$$R^{-}_{l,l^{\prime}}=\frac{1}{N}\sum_{i=1}^{N-1}x_{i}^{(l)}x_{i}^{(l^{\prime})},\quad\mbox{and}\quad\nu_{s}(f)=\operatorname{\mathbb{E}}\langle f\rangle_{t,s}.$$

In our last notation, we have only emphasized the dependence of the average on $s$; the parameter $t$ will henceforth remain fixed. Moreover, we write $\nu(f)$ for $\nu_{1}(f)$. The following three lemmas are variants of Lemma 1.6.3, Lemma 1.6.4 and Proposition 1.8.1 respectively in (Talagrand, 2011a, ).

Lemma 15.

For all $n\geq 1$,

$$\frac{\mathrm{d}}{\mathrm{d}s}\nu_{s}(f) =\frac{\lambda t}{2}\sum_{1\leq l\neq l^{\prime}\leq n}\nu_{s}((R^{-}_{l,l^{\prime}}-q)y^{(l)}y^{(l^{\prime})}f)-\lambda tn\sum_{l=1}^{n}\nu_{s}(R^{-}_{l,n+1}-q)y^{(l)}y^{(n+1)}f)$$

$$~{}~{}+\lambda tn\sum_{l=1}^{n}\nu_{s}((R^{-}_{l,*}-q)y^{(l)}y^{*}f)-\lambda tn\nu_{s}((R^{-}_{n+1,*}-q)y^{(n+1)}y^{*}f)$$

$$~{}~{}+\lambda t\frac{n(n+1)}{2}\nu_{s}((R^{-}_{n+1,n+2}-q)y^{(n+1)}y^{(n+2)}f),$$

where we have written $y=x_{N}$.

Proof.

The computation relies on Gaussian integration by parts. See (Talagrand, 2011a, , Lemma 1.6.3) for the details of a similar computation. $\blacksquare$

Lemma 16.

If $f$ is a bounded non-negative function, then for all $s\in[0,1]$,

$$\nu_{s}(f)\leq K(\lambda,n)\nu(f).$$

Proof.

Since the variables and the overlaps are all bounded, and $t\leq 1$, using Lemma 15 we have for all $s\in[0,1]$

$$|\nu_{s}^{\prime}(f)|\leq K(\lambda,n)\nu_{s}(f).$$

Then we conclude using Grönwall’s lemma. $\blacksquare$

Lemma 17.

For all $s\in[0,1]$, and all $\tau_{1},\tau_{2}>0$ such that $1/\tau_{1}+1/\tau_{2}=1$,

$$\left|\nu_{s}(f)-\nu_{0}(f)\right| \leq K(\lambda,n)\nu\left(\left|R^{-}_{1,*}-q\right|^{\tau_{1}}\right)^{1/\tau_{1}}\cdot\nu\left(|f|^{\tau_{2}}\right)^{1/\tau_{2}}$$ (38)

$$\left|\nu_{s}(f)-\nu_{0}(f)-\nu_{0}^{\prime}(f)\right| \leq K(\lambda,n)\nu\left(\left|R^{-}_{1,*}-q\right|^{\tau_{1}}\right)^{1/\tau_{1}}\cdot\nu\left(|f|^{\tau_{2}}\right)^{1/\tau_{2}}.$$ (39)

Proof.

We use Taylor’s approximations

$$\left|\nu_{s}(f)-\nu_{0}(f)\right| \leq\sup_{0\leq s\leq 1}\left|\nu^{\prime}_{s}(f)\right|,$$

$$\left|\nu_{s}(f)-\nu_{0}(f)-\nu_{0}^{\prime}(f)\right| \leq\sup_{0\leq s\leq 1}\left|\nu^{\prime\prime}_{s}(f)\right|,$$

then Lemma 15 and the triangle inequality to bound the right hand sides, then Hölder’s inequality to bound each term in the derivative, and then we apply Lemma 16. (To compute the second derivative, one need to use Lemma 15 recursively.) $\blacksquare$

5.2 The cavity matrix

Recall the parameters $a(0)$, $a(1)$ and $a(2)$ from (11):

$$a(0)=\operatorname{\mathbb{E}}\left[\langle x^{2}\rangle_{r}^{2}\right]-q^{*2}(\lambda),\quad a(1)=\operatorname{\mathbb{E}}\left[\langle x^{2}\rangle_{r}\langle x\rangle_{r}^{2}\right]-q^{*2}(\lambda),\quad a(2)=\operatorname{\mathbb{E}}\left[\langle x\rangle_{r}^{4}\right]-q^{*2}(\lambda),$$

where $r=\lambda q^{*}(\lambda)$. Now let

$$\bm{A}:=\lambda\cdot\begin{bmatrix}a(0)&-2a(1)&a(2)\\ a(1)&a(0)-a(1)-2a(2)&-2a(1)+3a(2)\\ a(2)&4a(1)-6a(2)&a(0)-6a(1)+6a(2)\end{bmatrix}\cdot$$ (40)

One can easily check that the transpose of this matrix has two eigenvalues $\mu_{1}$ and $\mu_{2}$ with expressions

$$\begin{aligned} \mu_{1}(\lambda)&=\lambda(a(0)-2a(1)+a(2)),\\ \mu_{2}(\lambda)&=\lambda(a(0)-3a(1)+2a(2)),\end{aligned}$$ (41)

and associated eigenvectors $(1,-2,1)$ and $(2,-3,2)$, and of multiplicities two and one respectively. (The first eigenvalue appears in a $2\times 2$ Jordan block.) We will need to control the largest eigenvalue of $\bm{A}^{\top}$. This matrix is the “planted” analogue of the one displayed in (Talagrand, 2011a, , equ. (1.234)) for the SK model. By Cauchy-Schwarz, $\mu_{1}-\mu_{2}=\lambda(a(1)-a(2))\geq 0$. As will be clear from the next subsection, the cavity computations we are about present are only informative when $\mu_{1}<1$. Interestingly, this is true for all values of $\lambda$ where the $\mathsf{RS}$ formula $\phi_{\mathsf{RS}}$ has two derivatives:

Lemma 18.

For all $\lambda\in\mathcal{A}$, $\mu_{1}(\lambda)<1$.

Proof.

First, if $\lambda<\lambda_{c}$, then $q^{*}(\lambda)=0$, and $\mu_{1}(\lambda)=\lambda(\operatorname{\mathbb{E}}_{P_{\textup{{x}}}}[X^{2}])^{2}$. By Lemma 1, $\mu_{1}(\lambda)<1$. Now we assume $\lambda\in\mathcal{A}\cap(\lambda_{c},+\infty)$. Recall

$$\psi(r)=\operatorname{\mathbb{E}}_{x^{*},z}\log\int\exp\left(\sqrt{r}zx+rxx^{*}-\frac{r}{2}x^{2}\right)\mathrm{d}P_{\textup{{x}}}(x),$$

and the $\mathsf{RS}$ potential

$$F(\lambda,q)=\psi(\lambda q)-\frac{\lambda q^{2}}{4}.$$

It is a straightforward exercise to compute the first and the second derivatives of $\psi$ using Gaussian integration by parts and the Nishimori property:

$$\psi^{\prime}(r)=\frac{1}{2}\operatorname{\mathbb{E}}\langle xx^{*}\rangle_{r},$$

$$\psi^{\prime\prime}(r)=\frac{1}{2}\left(\operatorname{\mathbb{E}}\langle x^{2}x^{*2}\rangle_{r}-2\operatorname{\mathbb{E}}\langle{x^{(1)}}^{2}x^{(2)}x^{*}\rangle_{r}+\operatorname{\mathbb{E}}\langle x^{(1)}x^{(2)}x^{(3)}x^{*}\rangle_{r}\right).$$

With the choice $r=\lambda q^{*}(\lambda)$, we see that $\mu_{1}(\lambda)=2\lambda\psi^{\prime\prime}(r)$. Now we observe that

$$\frac{\partial^{2}F}{\partial q^{2}}(\lambda,q)=\frac{\lambda}{2}(2\lambda\psi^{\prime\prime}(\lambda q)-1).$$

Since $q^{*}(\lambda)$ is a maximizer of the smooth function $F(\lambda,\cdot)$, and lies in the interior of its domain ($q^{*}(\lambda)>0$ for $\lambda>\lambda_{c}$), then it must be a first-order stationary point: $\frac{\partial F}{\partial q}(\lambda,q^{*})=0$. Hence $\frac{\partial^{2}F}{\partial q^{2}}(\lambda,q^{*})\leq 0$, i.e., $\mu_{1}(\lambda)\leq 1$ for all $\lambda>\lambda_{c}$. Now we claim that the inequality must be strict for $\lambda\in\mathcal{A}$. Indeed, (Lelarge and Miolane, , 2016, Proposition 15) show that whenever $\phi_{\mathsf{RS}}$ is differentiable at $\lambda$, then the maximizer of $F(\lambda,\cdot)$ is unique and

$$\phi_{\mathsf{RS}}^{\prime}(\lambda)=\frac{q^{*2}(\lambda)}{4}.$$

Therefore, twice differentiability of $\phi_{\mathsf{RS}}$ implies first differentiability of $\lambda\mapsto q^{*}(\lambda)$ whenever $q^{*}(\lambda)>0$ (i.e., $\lambda>\lambda_{c}$). Now we take advantage of first-order optimality: $\frac{\partial F}{\partial q}(\lambda,q^{*})=0$ is the same as

$$\psi^{\prime}(\lambda q^{*}(\lambda))=\frac{q^{*}(\lambda)}{2}.$$

The above can be seen as an equality of functions (of $\lambda$) defined almost everywhere. Taking one derivative yields

$$q^{*}(\lambda)\psi^{\prime\prime}(\lambda q^{*}(\lambda))=\frac{1}{2}\big{(}1-2\lambda\psi^{\prime\prime}(\lambda q^{*}(\lambda))\big{)}q^{*^{\prime}}(\lambda).$$

Since $q^{*}(\lambda)$ and $\psi^{\prime\prime}(\lambda q^{*}(\lambda))$ are both positive, the right-hand side cannot vanish. This concludes the proof. $\blacksquare$

5.3 Cavity computations for the second moment

In this subsection we prove the convergence of the second moment of the overlaps:

$$\nu((R_{1,*}-q^{*})^{2})\leq\frac{K}{N}+Ke^{-c(t)N},$$

with $c(t)\sim c_{0}(1-t)^{2}$ as $t\to 1$ when $\lambda>\lambda_{c}$ and $P_{\textup{{x}}}$ is symmetric about the origin, and uniformly lower-bounded by a positive constant otherwise. To lighten the notation in the calculations to come, $q^{*}(\lambda)$ will be denoted simply by $q$, and we recall the notation $\nu(\cdot)=\operatorname{\mathbb{E}}\langle\cdot\rangle_{t,1}$. Let

$$A=\nu\left((R_{1,*}-q)^{2}\right),~{}~{}~{}B=\nu\left((R_{1,*}-q)(R_{2,*}-q)\right),~{}~{}~{}C=\nu\left((R_{1,*}-q)(R_{2,3}-q)\right).$$

By symmetry between sites,

$$A=\nu\left((R_{1,*}-q)(x_{N}x_{N}^{*}-q)\right)=\frac{1}{N}\nu\left(x_{N}x_{N}^{*}(x_{N}x_{N}^{*}-q)\right)+\nu((R^{-}_{1,*}-q)(x_{N}x_{N}^{*}-q)).$$

By the first bound (38) of Lemma 17 with $\tau_{1}=1$, $\tau_{2}=\infty$, we get

$$\nu(x_{N}x_{N}^{*}(x_{N}x_{N}^{*}-q))=\nu_{0}(x_{N}x_{N}^{*}(x_{N}x_{N}^{*}-q))+\delta=a(0)+\delta,$$

with $|\delta|\leq K(\lambda)\nu(|R^{-}_{1,*}-q|)$. On the other hand, by the second bound (39) with $\tau_{1}=1$, $\tau_{2}=\infty$, we get

$$\nu((R^{-}_{1,*}-q)(x_{N}x_{N}^{*}-q))=\nu_{0}^{\prime}((R^{-}_{1,*}-q)(x_{N}x_{N}^{*}-q))+\delta.$$

This is because $\nu_{0}((R^{-}_{1,*}-q)(x_{N}x_{N}^{*}-q))=0$, since last variable $x_{N}$ decouples from the remaining $N-1$ variables under the measure $\nu_{0}$. Now, we use Lemma 15 with $n=1$, to evaluate the above derivative at $t=0$. We still write $y^{(l)}=x_{N}^{(l)}$.

$$\nu_{0}^{\prime}((R^{-}_{1,*}-q)(x_{N}x_{N}^{*}-q)) =-\lambda t\nu_{0}(y^{(1)}y^{(2)}(y^{(1)}y^{*}-q)(R^{-}_{1,*}-q)(R^{-}_{1,2}-q))$$

$$~{}~{}+\lambda t\nu_{0}(y^{(1)}y^{*}(y^{(1)}y^{*}-q)(R^{-}_{1,*}-q)^{2})$$

$$~{}~{}-\lambda t\nu_{0}(y^{(2)}y^{*}(y^{(1)}y^{*}-q)(R^{-}_{1,*}-q)(R^{-}_{2,*}-q))$$

$$~{}~{}+\lambda t\nu_{0}(y^{(2)}y^{(3)}(y^{(1)}y^{*}-q)(R^{-}_{1,*}-q)(R^{-}_{2,3}-q)).$$

We extract the average on the $y$-variables from the rest of the expression as pre-factors, so that the above is equal to

$$-\lambda ta(1)\nu_{0}((R^{-}_{1,*}-q)(R^{-}_{1,2}-q))+\lambda ta(0)\nu_{0}((R^{-}_{1,*}-q)^{2})$$

$$-\lambda ta(1)\nu_{0}((R^{-}_{1,*}-q)(R^{-}_{2,*}-q))+\lambda ta(2)\nu_{0}((R^{-}_{1,*}-q)(R^{-}_{2,3}-q)).$$

We notice that by the Nishimori property that

$$\nu_{0}((R^{-}_{1,*}-q)(R^{-}_{1,2}-q))=\nu_{0}((R^{-}_{1,*}-q)(R^{-}_{2,*}-q)).$$

Now we observe that $\nu_{0}^{\prime}((R^{-}_{1,*}-q)(x_{N}x_{N}^{*}-q))$ is a linear combination of terms that resemble, but are not quite equal to $A$, $B$ and $C$. We are nevertheless tempted to make the substitution since we expect them to be close. We use Lemma 17 to justify this. Taking $\nu_{0}((R^{-}_{1,*}-q)^{2})$ as an example, we apply the estimate (38) with $t=1$, $\tau_{1}=3$ and $\tau_{2}=3/2$. We get

$$\nu_{0}((R^{-}_{1,*}-q)^{2})=\nu((R^{-}_{1,*}-q)^{2})+\delta$$

with $|\delta|\leq K(\lambda)\nu(|R^{-}_{1,*}-q|^{3})$. Moreover,

$$\nu((R^{-}_{1,*}-q)^{2})=\nu((R_{1,*}-\frac{1}{N}yy^{*}-q)^{2})=\nu((R_{1,*}-q)^{2})-\frac{2}{N}\nu(yy^{*}(R_{1,*}-q))+\frac{1}{N^{2}}\nu({y}^{2}{y^{*}}^{2}).$$

The third term is of order $1/N^{2}$, and the second term is bounded by $\frac{1}{N}\nu_{0}(\left|R_{1,*}-q\right|)$. Therefore

$$\nu_{0}((R^{-}_{1,*}-q)^{2})=\nu((R_{1,*}-q)^{2})+\delta^{\prime},$$

with

$$|\delta^{\prime}|\leq K(\lambda)\left(\frac{1}{N}\nu(|R^{-}_{1,*}-q|)+\nu(|R^{-}_{1,*}-q|^{3})+\frac{1}{N^{2}}\right).$$

This argument applies equally to the remaining terms $\nu_{0}((R^{-}_{1,*}-q)(R^{-}_{2,*}-q))$ and $\nu_{0}((R^{-}_{1,*}-q)(R^{-}_{2,3}-q))$. We then end up with the identity

$$A=\frac{a(0)}{N}+\lambda^{\prime}a(0)A-2\lambda^{\prime}a(1)B+\lambda^{\prime}a(2)C+\delta(0),$$ (42)

where $\lambda^{\prime}=t\lambda$, and $|\delta(0)|$ is bounded by the same quantity as $|\delta^{\prime}|$.

Next, we apply the same reasoning to $B$ and $C$ as well, (e.g., Lemma 15 needs to applied with $n=2$ for $B$ and $n=3$ for $C$) we get

$$B =\frac{a(1)}{N}+\lambda^{\prime}a(1)A+\lambda^{\prime}(a(0)-a(1)-2a(2))B+\lambda^{\prime}(-2a(1)+3a(2))C+\delta(1),$$ (43)

$$C =\frac{a(2)}{N}+\lambda^{\prime}a(2)A+\lambda^{\prime}(4a(1)-6a(2))B+\lambda^{\prime}(a(0)-6a(1)+6a(2))C+\delta(2),$$ (44)

where for $i=0,1,2$,

$$|\delta(i)|\leq K(\lambda)\left(\frac{1}{N}\nu(|R^{-}_{1,*}-q|)+\nu(|R^{-}_{1,*}-q|^{3})+\frac{1}{N^{2}}\right).$$ (45)

We have ended up with a linear system in the quantities $A$, $B$ and $C$. Let $\bm{z}=[A,B,C]^{\top}$ and $\bm{\delta}=[\delta(0),\delta(1),\delta(2)]^{\top}$. Then the equations (42), (43) and (44) can be written as

$$\bm{z}=\frac{1}{N}\bm{a}+t\bm{A}\bm{z}+\bm{\delta},$$ (46)

where $\bm{a}=[a(0),a(1),a(2)]^{\top}$, and the matrix $\bm{A}$ are defined in (40). The above system implies useful bounds on the coefficients of the vector $\bm{z}$ only if the largest eigenvalue of the matrix $t\bm{A}$ is smaller than 1. This is insured by Lemma 18 when $\lambda\in\mathcal{A}$ (independently of $t$). Now we can invert the linear system and extract $\bm{z}$:

$$\bm{z}=\frac{1}{N}(\bm{I}-t\bm{A})^{-1}\bm{a}+(\bm{I}-t\bm{A})^{-1}\bm{\delta}.$$ (47)

Now we need to control the entries of $\bm{\delta}$. By elementary manipulations,

$$\nu(|R_{1,*}^{-}-q|)\leq\nu(|R_{1,*}-q|)+\frac{K}{N},$$

and

$$\nu(|R_{1,*}^{-}-q|^{3})\leq\nu(|R_{1,*}-q|^{3})+\frac{K}{N}\nu((R_{1,*}-q)^{2})+\frac{K}{N^{2}}\nu(|R_{1,*}-q|)+\frac{K}{N^{3}}.$$

Therefore, from (45) we have for all $i=0,1,2$,

$$|\delta(i)|\leq K\left(\nu(|R_{1,*}-q|^{3})+\frac{1}{N}\nu((R_{1,*}-q)^{2})+\frac{1}{N}\nu(|R_{1,*}-q|)+\frac{1}{N^{2}}\right).$$ (48)

Now we will argue that $\nu(|R_{1,*}-q|)\ll 1$ and $\nu(|R_{1,*}-q|^{3})\ll\nu((R_{1,*}-q)^{2})$. With Lemma 13 we have for $\epsilon>0$

$$\nu(|R_{1,*}-q|)\leq\epsilon+K(\epsilon)e^{-cN},$$

and

$$\nu(|R_{1,*}-q|^{3})\leq\epsilon\nu((R_{1,*}-q)^{2})+K(\epsilon)e^{-cN}.$$

Combining the above two bounds with (48), and then injecting in (47), we get

$$\nu((R_{1,*}-q)^{2})=z(0) \leq\left\|z\right\|_{\ell_{2}}\leq\left\|\frac{1}{N}(\bm{I}-t\bm{A})^{-1}\bm{a}\right\|_{\ell_{2}}+\left\|(\bm{I}-t\bm{A})^{-1}\right\|_{\text{op}}\left\|\bm{\delta}\right\|_{\ell_{2}}$$

$$\leq\frac{\left\|\bm{c}\right\|_{\ell_{2}}}{N}+K(\epsilon+\frac{1}{N})\nu((R_{1,*}-q)^{2})+K(\epsilon)e^{-cN}.$$

The symbols $\left\|\cdot\right\|_{\ell_{2}}$ and $\|\cdot\|_{\text{op}}$ refer to the $\ell_{2}$ norm of a vector and the matrix operator norm respectively. Here, $\bm{c}=(\bm{I}-t\bm{A})^{-1}\bm{a}$. Note that the matrix inverses are bounded even as $t\to 1$ since $\mu_{1}<1$ for $\lambda\in\mathcal{A}$. We choose $\epsilon$ small enough and $N$ large enough that $K(\epsilon+\frac{1}{N})<1$. We therefore get

$$\nu\left((R_{1,*}-q)^{2}\right)\leq\frac{K(\lambda)}{N}+K(\lambda)e^{-c(t)N}.$$

5.4 Cavity computations for the fourth moment

In this subsection we prove the convergence of the fourth moment:

$$\nu((R_{1,*}-q^{*})^{4})\leq\frac{K}{N^{2}}+Ke^{-c(t)N},$$

where $c(t)$ is of the same type as before. We adopt the same technique based on the cavity method, with the extra knowledge that the second moment converges. Many parts of the argument are exactly the same so we will only highlight the main novelties in the proof. Let

$$A=\nu\left((R_{1,*}-q)^{4}\right),~{}~{}~{}B=\nu\left((R_{1,*}-q)^{3}(R_{2,*}-q)\right),~{}~{}~{}C=\nu\left((R_{1,*}-q)^{3}(R_{2,3}-q)\right).$$

By symmetry between sites,

$$A =\nu\left((R_{1,*}-q)^{3}(x_{N}x_{N}^{*}-q)\right)$$

$$=\nu((R^{-}_{1,*}-q)^{3}(x_{N}x_{N}^{*}-q))+\frac{3}{N}\nu((R^{-}_{1,*}-q)^{2}x_{N}x_{N}^{*}(x_{N}x_{N}^{*}-q))$$

$$~{}~{}~{}+\frac{3}{N^{2}}\nu((R^{-}_{1,*}-q){x_{N}}^{2}{x_{N}^{*}}^{2}(x_{N}x_{N}^{*}-q))+\frac{1}{N^{3}}\nu({x_{N}}^{3}{x_{N}^{*}}^{3}(x_{N}x_{N}^{*}-q)).$$

The quadratic term is bounded as

$$\nu((R^{-}_{1,*}-q)^{2}x_{N}x_{N}^{*}(x_{N}x_{N}^{*}-q))\leq K\nu((R^{-}_{1,*}-q)^{2})\leq\frac{K}{N}+Ke^{-cN}.$$

The last inequality is using our extra knowledge about the convergence of the second moment. The last two terms are also bounded by $K/N^{2}$ and $K/N^{3}$ respectively. Now we must deal with the cubic term, and here, we apply the exact same technique used to deal with the term $\nu((R^{-}_{1,*}-q)(x_{N}x_{N}^{*}-q))$ in the previous proof. The argument goes verbatim. Then we equally treat the terms $B$ and $C$. We end up with a similar linear system relating $A$, $B$ and $C$:

$$\bm{z}=\frac{1}{N^{2}}\bm{d}+t\bm{A}\bm{z}+\bm{\delta},$$

where $\bm{z}=[A,B,C]^{\top}$. The differences with the earlier linear system (46) are in the vector of coefficients $\bm{d}$ (that could be determined from the recursions) and the error terms $\delta(i)$, which are now bounded as

$$|\delta(i)|\leq K\nu(|R^{-}_{1,*}-q|^{5})+K\sum_{l=1}^{3}\frac{1}{N^{3-l}}\nu(|R^{-}_{1,*}-q|^{l}).$$

Crucially, the matrix $\bm{A}$ remains the same. Using Lemma 13, we have for $\epsilon>0$,

$$\nu(|R_{1,*}-q|^{5})\leq\epsilon\nu((R_{1,*}-q)^{4})+K(\epsilon)e^{-cN},$$

$$\nu(|R_{1,*}-q|^{3})\leq\epsilon\nu((R_{1,*}-q)^{2})+K(\epsilon)e^{-cN}.$$

With the bound we already have on $\nu((R_{1,*}-q)^{2})$, we finish the argument in the same way, by choosing $\epsilon$ sufficiently small. This concludes the proof of Theorem 7.

5.5 Sharper results: the asymptotic variance

Finally, given the convergence of the fourth moment, we can refine the convergence result of the second moment. Indeed we are now able to compute the limit of $N\cdot\nu((R_{1,*}-q)^{2})$. Using Jensen’s inequality on the second and fourth moment, we have

$$\nu(|R_{1,*}-q|)\leq\frac{K}{\sqrt{N}}+Ke^{-c(t)N},~{}~{}~{}\mbox{and}~{}~{}~{}\nu(|R_{1,*}-q|^{3})\leq\frac{K}{N^{3/2}}+Ke^{-c^{\prime}(t)N}.$$

Looking back at (48), we can now assert that

$$|\delta(i)|\leq\frac{K}{N^{3/2}}+Ke^{-c(t)N}.$$

We plug this new knowledge in (47), and obtain

$$\left\|N\bm{z}-(\bm{I}-t\bm{A})^{-1}\bm{a}\right\|_{\ell_{2}} \leq N\left\|(\bm{I}-t\bm{A})^{-1}\right\|_{\text{op}}\left\|\bm{\delta}\right\|_{\ell_{2}}\leq K\Big{(}\frac{1}{\sqrt{N}}+Ne^{-c(t)N}\Big{)}.$$

The last line follows since $\sup_{t}\left\|(\bm{I}-t\bm{A})^{-1}\right\|_{\text{op}}\leq K(\lambda)$ for $\lambda\in\mathcal{A}$. We have just proved that

$$\nu((R_{1,*}-q)^{2}) =\frac{c(0)}{N}+K(\lambda)\Big{(}\frac{1}{N^{3/2}}+e^{-c(t)N}\Big{)},$$

$$\nu((R_{1,*}-q)(R_{2,*}-q)) =\frac{c(1)}{N}+K(\lambda)\Big{(}\frac{1}{N^{3/2}}+e^{-c(t)N}\Big{)},$$

$$\nu((R_{1,*}-q)(R_{2,3}-q)) =\frac{c(2)}{N}+K(\lambda)\Big{(}\frac{1}{N^{3/2}}+e^{-c(t)N}\Big{)},$$

where $\bm{c}=(\bm{I}-t\bm{A})^{-1}\bm{a}$. One can solve this linear system explicitly and obtain the expression of the coordinates of $\bm{c}$:

$$c(0) =\frac{1}{\lambda t}\left(-1+\frac{2}{1-t\mu_{2}}+\frac{2}{1-t\mu_{1}}+\frac{-3+3\lambda ta(0)-2\lambda ta(1)}{(1-t\mu_{1})^{2}}\right),$$

$$c(1) =\frac{1}{\lambda t}\left(\frac{-3+3\lambda ta(0)-2\lambda ta(1)}{(1-t\mu_{1})^{2}}+\frac{3}{1-t\mu_{2}}\right),$$

$$c(2) =\frac{4\lambda ta(1)^{2}+(1-\lambda ta(0)-5\lambda ta(1))a(2)+2\lambda ta(2)^{2}}{(1-t\mu_{1})^{2}(1-t\mu_{2})}.$$

The expression of the first coordinate defines $\Delta_{\mathsf{RS}}(\lambda;t)$, equ.(27). This concludes the proof of Theorem 8.

5.6 Proof of Lemma 9

Let $f(x,x^{*})=x^{2}x^{*2}$. We have $\nu_{0}(f)=a(0)$. We use the first assertion of Lemma 17 with $\tau_{1}=1$ and $\tau_{2}=\infty$ to get

$$\left|\nu(f)-\nu_{0}(f)\right|\leq K(\lambda)\nu(|R_{1,*}^{-}-q^{*}|)\leq\frac{K}{\sqrt{N}}+Ke^{-c(t)N},$$

where the last bound follows from Theorem 7 and Jensen’s inequality.

6 Proof of Theorem 4

In this section we prove a slightly stronger result than convergence in distribution. We prove the convergence of all moments with an explicit rate of $\mathcal{O}(N^{-1/2})$. Statement $(ii)$ is deduced effortlessly form a classical result while statement $(i)$ requires more work. We start with the former.

6.1 Fluctuations under $\operatorname{\mathbb{P}}_{0}$: the ALR CLT

We assume in this subsection that $P_{\textup{{x}}}=\frac{1}{2}\delta_{-1}+\frac{1}{2}\delta_{+1}$, and let $\bm{Y}\sim\operatorname{\mathbb{P}}_{0}$, i.e, $Y_{ij}\sim\mathcal{N}(0,1)$ i.i.d. We then see that the likelihood ratio is related to the partition function of the Sherrington–Kirkpatrick model via a trivial relation:

$$\log L(\bm{Y};\lambda) =\log\int\exp\Big{(}\sqrt{\frac{\lambda}{N}}\sum_{i<j}Y_{ij}x_{i}x_{j}-\frac{\lambda}{2N}\sum_{i<j}x_{i}^{2}x_{j}^{2}\Big{)}~{}\mathrm{d}P_{\textup{{x}}}^{\otimes N}(\bm{x})$$

$$=\log\sum_{\bm{\sigma}\in\{\pm 1\}^{N}}\exp\Big{(}\frac{\beta}{\sqrt{N}}\sum_{i<j}Y_{ij}\sigma_{i}\sigma_{j}\Big{)}-N\log 2-\frac{\beta^{2}(N-1)}{4}$$

$$=:\log Z_{N}(\beta)-N\log 2-\frac{\beta^{2}(N-1)}{4},$$

where we have let $\beta=\sqrt{\lambda}$. $Z_{N}(\beta)$ is the partition function of the SK model at inverse temperature $\beta>0$. It is easy to compute the expectation of $Z_{N}(\beta)$:

$$\log\operatorname{\mathbb{E}}Z_{N}(\beta)=N\log 2+\frac{\beta^{2}(N-1)}{4},$$

so that $\operatorname{\mathbb{E}}\log L(\bm{Y};\lambda)$ is the gap between the free energy of the SK model and its annealed version. The question of determining the values of the inverse temperature for which this gap is zero (or constant), i.e., at what temperatures is the free energy given by the annealed computation? is a central question in statistical physics. Aizenman, Lebowitz and Ruelle (ALR) proved that in the high-temperature regime $\beta<1$, $\log(Z_{N}(\beta)/\operatorname{\mathbb{E}}Z_{N}(\beta))$ converges in distribution the normal law

$$\mathcal{N}\left(\frac{1}{4}(\log(1-\beta^{2})+\beta^{2}),-\frac{1}{2}(\log(1-\beta^{2})+\beta^{2})\right).$$

In our notation this simply means

$$\log L(\bm{Y};\lambda)\rightsquigarrow\mathcal{N}(-\mu,\sigma^{2})$$

under $\operatorname{\mathbb{P}}_{0}$ where $\mu=\frac{1}{2}\sigma^{2}=-\frac{1}{4}(\log(1-\lambda)+\lambda)$. The ALR proof is combinatorial and uses so-called cluster expansion techniques. It may not extend to other types of priors. Alternative proofs were subsequently found by adopting different perspectives on the problem (Comets and Neveu, , 1995; Guerra and Toninelli, 2002a, ). A more recent proof based on the cavity method is provided by Talagrand in his second book (Talagrand, 2011b, , Section 11.4). His method provides an explicit (and optimal) rate of convergence of the moments of the random variable in question to those of the Gaussian. In what follows we use Talagrand’s approach to prove a similar central limit theorem when $\bm{Y}\sim\operatorname{\mathbb{P}}_{\lambda}$, for an arbitrary bounded prior $P_{\textup{{x}}}$. In this more general setting, the high temperature region of the model is given by the condition $\lambda<\lambda_{c}$.

6.2 Fluctuations under $\operatorname{\mathbb{P}}_{\lambda}$: a planted version of the ALR CLT

Let $\lambda<\lambda_{c}$, and $\bm{Y}\sim\operatorname{\mathbb{P}}_{\lambda}$. We define the random variable

$$X(\lambda)=\log L(\bm{Y})-\mu(\lambda),$$

where

$$\mu(\lambda)=\frac{1}{4}(-\log(1-\lambda)-\lambda),\quad\mbox{and}\quad b(\lambda)=\sigma^{2}(\lambda)=2\mu(\lambda).$$

We will prove that the integer moments of $X(\lambda)$ converge to those of the Gaussian with variance $b(\lambda)$. This is a sufficient condition for convergence in distribution to hold, since the Gaussian is uniquely determined by its moments.

Theorem 19.

For all $\lambda<\lambda_{c}$ and integers $k$, there exists a constant $K(\lambda,k)\geq 0$ such that

$$\left|\operatorname{\mathbb{E}}\left[X(\lambda)^{k}\right]-m(k)b(\lambda)^{k/2}\right|\leq\frac{K(\lambda,k)}{\sqrt{N}},$$

where $m(k)=\operatorname{\mathbb{E}}[g^{k}]$ is the $k$-th moment of the standard Gaussian $g\sim\mathcal{N}(0,1)$.

This theorem mirrors Theorem 11.4.1 in (Talagrand, 2011b, ), and our approach is inspired by his. We define the function

$$f(\lambda):=\operatorname{\mathbb{E}}\left[X(\lambda)^{k}\right].$$

Lemma 20.

For all $\lambda<\lambda_{c}$,

$$f^{\prime}(\lambda) =-\frac{k}{4}\operatorname{\mathbb{E}}\left[\left(N\langle R_{1,2}^{2}\rangle-\langle x_{N}^{2}\rangle^{2}\right)X(\lambda)^{k-1}\right]+\frac{k}{2}\operatorname{\mathbb{E}}\left[\left(N\langle R_{1,*}^{2}\rangle-\langle x_{N}^{2}x_{N}^{*2}\rangle\right)X(\lambda)^{k-1}\right]$$

$$~{}~{}~{}-k\mu^{\prime}(\lambda)\operatorname{\mathbb{E}}\left[X(\lambda)^{k-1}\right]+\frac{k(k-1)}{4}\operatorname{\mathbb{E}}\left[\left(N\langle R_{1,2}^{2}\rangle-\langle x_{N}^{2}\rangle^{2}\right)X(\lambda)^{k-2}\right].$$ (49)

Proof.

This is by simple differentiation and regrouping of terms. $\blacksquare$

The derivative involves averages of the form

$$\operatorname{\mathbb{E}}\left[\left(N\langle R_{1,l}^{2}\rangle-\langle{x^{(1)}_{N}}^{2}{x^{(l)}_{N}}^{2}\rangle\right)X(\lambda)^{k}\right],$$

for $l=2,*$. In the first line of (20), we see that the planted term $l=*$ has a pre-factor twice as big the that of the replica term $l=2$. This is the reason the mean of the limiting Gaussian is $\mu$ and not $-\mu$ in the planted case. A crucial step in the argument is to show that $X(\lambda)^{k}$ and its pre-factor in the above expression are asymptotically uncorrelated, so that one can split the expectation:

Proposition 21.

For all $\lambda<\lambda_{c}$ and integers $k\geq 1$, and $l\in\{2,*\}$, we have

$$\operatorname{\mathbb{E}}\left[\left(N\langle R_{1,l}^{2}\rangle-\langle{x^{(1)}_{N}}^{2}{x^{(l)}_{N}}^{2}\rangle\right)X(\lambda)^{k}\right]=\frac{\lambda}{1-\lambda}\operatorname{\mathbb{E}}\left[X(\lambda)^{k}\right]+\delta,$$

where $|\delta|\leq K(k,\lambda)/\sqrt{N}$.

Proof of Theorem 19. Proposition 21 implies

$$f^{\prime}(\lambda)=k\left(\frac{1}{4}\frac{\lambda}{1-\lambda}-\mu^{\prime}(\lambda)\right)\operatorname{\mathbb{E}}\left[X(\lambda)^{k-1}\right]+\frac{k(k-1)}{4}\frac{\lambda}{1-\lambda}\operatorname{\mathbb{E}}\left[X(\lambda)^{k-2}\right]+\delta.$$

Notice that with our choice of the function $\mu$, the first term on the right-hand side vanishes. (Setting this term to zero provides another way of discovering the function $\mu$.) Now we let $b(\lambda)=2\mu(\lambda)$. We have for all $\lambda$ and all $k\geq 2$

$$\frac{\mathrm{d}}{\mathrm{d}\lambda}\operatorname{\mathbb{E}}\left[X(\lambda)^{k}\right]=\frac{k(k-1)}{2}b^{\prime}(\lambda)\operatorname{\mathbb{E}}\left[X(\lambda)^{k-2}\right]+\delta.$$ (50)

By induction, and since $X(0)=0$, we see that for all even $k$

$$\operatorname{\mathbb{E}}\left[X(\lambda)^{k}\right]=m(k)b(\lambda)^{k/2}+\mathcal{O}\left(\frac{K(k,\lambda)}{\sqrt{N}}\right),$$

where $m(k)=(k-1)m(k-2)$ and $m(0)=1$. The last recursion defines the sequence of even Gaussian moments. As for odd values of $k$, we have already proved in Corollary 3 that

$$\left|\operatorname{\mathbb{E}}\left[X(\lambda)\right]\right|\leq\frac{K(\lambda)}{\sqrt{N}}.$$

We use induction again on (50) to conclude that for all odd $k$,

$$\left|\operatorname{\mathbb{E}}\left[X(\lambda)^{k}\right]\right|\leq\frac{K(k,\lambda)}{\sqrt{N}}.$$

 

6.3 Proof of Proposition 21

The argument is in two stages. We first prove that

$$N\cdot\operatorname{\mathbb{E}}\left[\langle R_{1,l}^{2}\rangle X(\lambda)^{k}\right]=\frac{1}{1-\lambda}\operatorname{\mathbb{E}}\left[\langle{x^{(1)}_{N}}^{2}{x^{(l)}_{N}}^{2}\rangle X(\lambda)^{k}\right]+\delta,$$ (51)

and then

$$\operatorname{\mathbb{E}}\left[\langle{x^{(1)}_{N}}^{2}{x^{(l)}_{N}}^{2}\rangle X(\lambda)^{k}\right]=\operatorname{\mathbb{E}}\left[X(\lambda)^{k}\right]+\delta,$$ (52)

where in both cases $|\delta|\leq K(k,\lambda)/\sqrt{N}$. We once again use the cavity method to extract the last variable $x_{N}$ and analyze its influence. Let

$$-H_{t}(\bm{x}) :=\sum_{1\leq i<j\leq N-1}-\frac{\lambda}{2N}x_{i}^{2}x_{j}^{2}+\sqrt{\frac{\lambda}{N}}W_{ij}x_{i}x_{j}+\frac{\lambda}{N}x_{i}x_{i}^{*}x_{j}x_{j}^{*}$$

$$~{}~{}~{}+\sum_{i=1}^{N-1}-\frac{t\lambda}{2N}x_{i}^{2}x_{N}^{2}+\sqrt{\frac{t\lambda}{N}}W_{iN}x_{i}x_{N}+\frac{t\lambda}{N}x_{i}x_{i}^{*}x_{N}x_{N}^{*},$$

and

$$Y(t):=\log\int e^{-H_{t}(\bm{x})}\mathrm{d}P_{\textup{{x}}}^{\otimes N}(\bm{x})-\mu(\lambda).$$

We have $Y(1)=X(\lambda)$. We consider the quantity

$$\varphi(t;l):=\operatorname{\mathbb{E}}\left[\left(N\langle R_{1,l}^{2}\rangle_{t}-\langle{x^{(1)}_{N}}^{2}{x^{(l)}_{N}}^{2}\rangle_{t}\right)Y(t)^{k}\right].$$

Our strategy is approximate $\varphi(t;l)$ by $\varphi(0;l)+\varphi^{\prime}(0;l)$. The approach is very similar to the one used to prove optimal rates of convergence of the overlaps. By symmetry between sites, we have

$$\varphi(t;l)=N\operatorname{\mathbb{E}}\left[\left\langle x_{N}^{(1)}x_{N}^{(l)}R_{1,l}^{-}\right\rangle_{t}Y(t)^{k}\right].$$

Notice that since the last variables decouple from the rest of the system at $t=0$, we have

$$\varphi(0;l) =N\operatorname{\mathbb{E}}\left[\langle x_{N}^{(1)}x_{N}^{(l)}\rangle_{0}\right]\cdot\operatorname{\mathbb{E}}\left[\left\langle R_{1,l}^{-}\right\rangle_{0}Y(0)^{k}\right]$$

$$=N\operatorname{\mathbb{E}}_{P_{\textup{{x}}}}[X]^{2}\cdot\operatorname{\mathbb{E}}\left[\left\langle R_{1,l}^{-}\right\rangle_{0}Y(0)^{k}\right]=0.$$

The expressions of the derivatives are a bit cumbersome so we do not display them, but we will describe their main features. From here onwards, we present the proof of (51) and  (52) for $l=2$ for concreteness. The exact same argument goes through for $l=*$. The only difference is in the number of terms showing up the derivatives of $\varphi$, not their nature. The derivative $\varphi^{\prime}(t;2)$ will be a sum of different terms, all of the form

$$\lambda Nc(k)\operatorname{\mathbb{E}}\left[\left\langle R^{-}_{1,2}R^{-}_{a,b}x_{N}^{(1)}x_{N}^{(2)}x_{N}^{(a)}x_{N}^{(b)}\right\rangle_{t}Y(t)^{n}\right],$$ (53)

where $n\in\{k-2,k-1,k\}$ and $(a,b)\in\{(1,2),(1,3),(3,4),(1,*),(3,*)\}$, and $c(k)$ is a polynomial of degree $\leq 2$ in $k$. We see that at $t=0$, if the above expression involves a variable $x_{N}$ of degree 1 then this term vanishes. Therefore the only remaining term is the one where $(a,b)=(1,2)$. One can verify that $c(k)=1$ for this term. Therefore

$$\varphi^{\prime}(0;2) =\lambda N\operatorname{\mathbb{E}}\left[\langle{x_{N}^{(1)}}^{2}{x_{N}^{(2)}}^{2}\rangle_{0}\right]\cdot\operatorname{\mathbb{E}}\left[\langle(R_{1,l}^{-})^{2}\rangle_{0}Y(0)^{k}\right]$$

$$=\lambda N\operatorname{\mathbb{E}}_{P_{\textup{{x}}}}\left[X^{2}\right]^{2}\cdot\operatorname{\mathbb{E}}\left[\langle(R_{1,l}^{-})^{2}\rangle_{0}Y(0)^{k}\right]$$

$$=\lambda N\operatorname{\mathbb{E}}\left[\langle(R_{1,l}^{-})^{2}\rangle_{0}Y(0)^{k}\right].$$ (54)

Now we turn to $\varphi^{\prime\prime}(t;2)$. Taking another derivative generates monomials of degree three in the overlaps and the last variable, so $\varphi^{\prime\prime}(t;2)$ is a sum of terms of the form

$$\lambda^{2}Nc^{\prime}(k)\operatorname{\mathbb{E}}\left[\left\langle R^{-}_{1,2}R^{-}_{a,b}R^{-}_{c,d}x_{N}^{(1)}x_{N}^{(2)}x_{N}^{(a)}x_{N}^{(b)}x_{N}^{(c)}x_{N}^{(d)}\right\rangle_{t}Y(t)^{n}\right],$$ (55)

where $c^{\prime}(k)$ is a polynomial of degree $\leq 3$ in $k$, and $n\in\{k-3,k-2,k-1,k\}$. Our goal is to bound the second derivative independently of $t$, so that we are able to use the Taylor approximation

$$\left|\varphi(1;2)-\varphi(0;2)-\varphi^{\prime}(0;2)\right|\leq\sup_{0\leq t\leq 1}\left|\varphi^{\prime\prime}(t;2)\right|.$$ (56)

Since prior $P_{\textup{{x}}}$ has bounded support, Hölder’s inequality implies that (55) is bounded by

$$NK(k,\lambda) \operatorname{\mathbb{E}}\left[\left\langle\left|R^{-}_{1,2}R^{-}_{a,b}R^{-}_{c,d}\right|\right\rangle_{t}^{p}\right]^{1/p}\operatorname{\mathbb{E}}\left[|Y(t)|^{nq}\right]^{1/q}$$

$$\leq NK(k,\lambda)\operatorname{\mathbb{E}}\left[\left\langle|R^{-}_{1,2}|^{3p}\right\rangle_{t}\right]^{1/p}\operatorname{\mathbb{E}}\left[|Y(t)|^{nq}\right]^{1/q},$$

where $1/p+1/q=1$. The last bound follows from Jensen’s inequality (since $p\geq 1$) and another application of Hölder’s inequality. We let $p=4/3$ and $q=4$. Using a straightforward analogue of Lemma 16 for the measure $\operatorname{\mathbb{E}}\langle\cdot\rangle_{t}$, and the convergence of the fourth moment, Theorem 7, we have

$$\operatorname{\mathbb{E}}\left\langle(R^{-}_{1,2})^{4}\right\rangle_{t}\leq K(\lambda)\operatorname{\mathbb{E}}\left\langle(R^{-}_{1,2})^{4}\right\rangle\leq\frac{K(\lambda)}{N^{2}}.$$

We use the following lemma to bound the moments of $Y(t)$:

Lemma 22.

For all $\lambda<\lambda_{c}$ and integers $k$, there exists a constant $K(k,\lambda)\geq 0$ such that for all $t\in[0,1]$

$$\operatorname{\mathbb{E}}\left[Y(t)^{2k}\right]\leq K(k,\lambda).$$

Proof.

Taking a derivative w.r.t. time, we have

$$\frac{\mathrm{d}}{\mathrm{d}t}\operatorname{\mathbb{E}}\left[Y(t)^{k}\right]= -\frac{\lambda k}{2}\operatorname{\mathbb{E}}\left[\left\langle x_{N}^{(1)}x_{N}^{(2)}R_{1,2}^{-}\right\rangle_{t}Y(t)^{k-1}\right]+\lambda k\operatorname{\mathbb{E}}\left[\left\langle x_{N}^{(1)}x_{N}^{*}R_{1,*}^{-}\right\rangle_{t}Y(t)^{k-1}\right]$$

$$+\frac{\lambda k(k-1)}{2}\operatorname{\mathbb{E}}\left[\left\langle x_{N}^{(1)}x_{N}^{(2)}R_{1,2}^{-}\right\rangle_{t}Y(t)^{k-2}\right].$$

By Hölder’s inequality and boundedness of the variables and overlaps,

$$\left|\frac{\mathrm{d}}{\mathrm{d}t}\operatorname{\mathbb{E}}\left[Y(t)^{k}\right]\right|\leq K(k,\lambda)\left(\operatorname{\mathbb{E}}\left[|Y(t)|^{k}\right]^{1-1/k}+\operatorname{\mathbb{E}}\left[|Y(t)|^{k}\right]^{1-2/k}\right).$$

The first term is generated by the terms involving $Y(t)^{k-1}$ in the derivative, and the second term comes from the one involving $Y(t)^{k-2}$. Since $k$ is even, we drop the absolute values on the right-hand side. Next, use the fact $x^{a}\leq 1+x$ for all $x\geq 0$ and $0\leq a\leq 1$, then we use Grönwall’s lemma to conclude. $\blacksquare$

Therefore by the above estimates we have

$$\sup_{0\leq t\leq 1}|\varphi^{\prime\prime}(t;2)|\leq\frac{K(k,\lambda)}{\sqrt{N}}.$$ (57)

Now, our next goal is to prove

$$\left|\varphi^{\prime}(0;2)-\lambda N\operatorname{\mathbb{E}}\left[\langle R_{1,2}^{2}\rangle X(\lambda)^{k}\right]\right|\leq\frac{K(k,\lambda)}{\sqrt{N}}.$$ (58)

We consider the function (this should come with no surprise at this point)

$$\psi(t):=\lambda N\operatorname{\mathbb{E}}\left[\left\langle(R_{1,2}^{-})^{2}\right\rangle_{t}Y(t)^{k}\right].$$

Observe that (54) tells us $\psi(0)=\varphi^{\prime}(0;2)$. On the other hand,

$$\left|\psi(1)-\lambda N\operatorname{\mathbb{E}}\left[\langle R_{1,2}^{2}\rangle X(\lambda)^{k}\right]\right|\leq 2\lambda\operatorname{\mathbb{E}}\left[\left\langle\left|R_{1,2}^{-}x_{N}^{(1)}x_{N}^{(2)}\right|\right\rangle|X(\lambda)|^{k}\right]+\frac{\lambda}{N}\operatorname{\mathbb{E}}\left[\left\langle{x_{N}^{(1)}}^{2}{x_{N}^{(2)}}^{2}\right\rangle|X(\lambda)|^{k}\right].$$

Using Lemma 22 and Hölder’s inequality, the first term is bounded by $K(k,\lambda)(\operatorname{\mathbb{E}}\langle(R_{1,2}^{-})^{2}\rangle)^{1/2}\leq K(k,\lambda)/\sqrt{N}$, and the second term is bounded by $K(k,\lambda)/N$. So it suffices to show that

$$\sup_{0\leq t\leq 1}|\psi^{\prime}(t)|\leq\frac{K(k,\lambda)}{\sqrt{N}}.$$

Similarly to $\varphi$, the derivative of $\psi$ is a sum of terms of the form

$$\lambda^{2}Nc(k)\operatorname{\mathbb{E}}\left[\left\langle(R^{-}_{1,2})^{2}R^{-}_{a,b}x_{N}^{(a)}x_{N}^{(b)}\right\rangle_{t}Y(t)^{n}\right].$$

It is clear that the same method used to bound $\varphi^{\prime\prime}$ (the generic term of which is (55)) also works in this case, so we obtain the desired bound on $\psi^{\prime}$. Finally, using (56), (57) and (58), we obtain

$$N\operatorname{\mathbb{E}}\left[\langle R_{1,2}^{2}\rangle X(\lambda)^{k}\right]-\operatorname{\mathbb{E}}\left[\langle{x^{(1)}_{N}}^{2}{x^{(2)}_{N}}^{2}\rangle X(\lambda)^{k}\right]=\lambda N\operatorname{\mathbb{E}}\left[\langle R_{1,2}^{2}\rangle X(\lambda)^{k}\right]+\delta,$$

where $|\delta|\leq K(k,\lambda)/\sqrt{N}$. This is equivalent to (51) and closes the first stage of the argument. Now we need to show that

$$\operatorname{\mathbb{E}}\left[\langle{x^{(1)}_{N}}^{2}{x^{(2)}_{N}}^{2}\rangle X(\lambda)^{k}\right]=\operatorname{\mathbb{E}}\left[X(\lambda)^{k}\right]+\delta.$$

The argument has become a routine by now: we consider the function

$$\psi(t)=\operatorname{\mathbb{E}}\left[\langle{x^{(1)}_{N}}^{2}{x^{(2)}_{N}}^{2}\rangle_{t}Y(t)^{k}\right].$$

We have

$$\psi(0)=\operatorname{\mathbb{E}}\left[\langle{x^{(1)}_{N}}^{2}{x^{(2)}_{N}}^{2}\rangle_{0}\right]\cdot\operatorname{\mathbb{E}}\left[Y(0)^{k}\right]=\operatorname{\mathbb{E}}_{P_{\textup{{x}}}}[X^{2}]^{2}\cdot\operatorname{\mathbb{E}}\left[Y(0)^{k}\right]=\operatorname{\mathbb{E}}\left[Y(0)^{k}\right].$$

The derivative of $\psi$ is a sum of term of the form

$$\lambda c(k)\operatorname{\mathbb{E}}\left[\left\langle{x^{(1)}_{N}}^{2}{x^{(2)}_{N}}^{2}R^{-}_{a,b}x_{N}^{(a)}x_{N}^{(b)}\right\rangle_{t}Y(t)^{n}\right].$$

By our earlier argument, $|\psi^{\prime}(t)|\leq K(k,\lambda)/\sqrt{N}$ for all $t$. We similarly argue that $\left|\frac{\mathrm{d}}{\mathrm{d}t}\operatorname{\mathbb{E}}[Y(t)^{k}]\right|\leq K(k,\lambda)/\sqrt{N}$ for all $t$, so that

$$\left|\psi(1)-\operatorname{\mathbb{E}}\left[Y(1)^{k}\right]\right|\leq\frac{K(k,\lambda)}{\sqrt{N}}.$$

This yields (52) and thus concludes the proof.

Appendix A Appendix

Here, we prove Lemma 10. A straightforward calculation reveals that

$$\frac{\partial}{\partial s}\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{3.65486pt}{0.43057pt}}{\psi}(r,s)=\operatorname{\mathbb{E}}\left[\langle xx^{*}\rangle\right],\quad\mbox{and}\quad\frac{\partial^{2}}{\partial s^{2}}\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{3.65486pt}{0.43057pt}}{\psi}(r,s)=\operatorname{\mathbb{E}}\left[x^{*2}(\langle x^{2}\rangle-\langle x\rangle^{2})\right]>0,$$

so that $s\mapsto\frac{\partial}{\partial s}\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{3.65486pt}{0.43057pt}}{\psi}(r,s)$ is Lipschitz and strongly convex on any interval, and for all $r\geq 0$.

Let $\nu=P_{\textup{{x}}}$, and let $\mu$ be the symmetric part of $P_{\textup{{x}}}$, i.e., $\mu(A)=(P_{\textup{{x}}}(A)+P_{\textup{{x}}}(-A))/2$ for all Borel $A\subseteq\mathbb{R}$. We observe that $\nu$ is absolutely continuous with respect to $\mu$, so that the Radon-Nikodym derivative $\frac{\mathrm{d}\nu}{\mathrm{d}\mu}$ is a well-defined measurable function from $\mathbb{R}$ to $\mathbb{R}_{+}$ that integrates to one.

Proposition 23.

For all $r\geq 0$, we have

$$\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{3.65486pt}{0.43057pt}}{\psi}(r,r)-\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{3.65486pt}{0.43057pt}}{\psi}(r,-r)\geq 2\operatorname{\mathbb{E}}\left[\left\langle\frac{\mathrm{d}\nu}{\mathrm{d}\mu}(x)-1\right\rangle_{\mu,r}^{2}\right],$$

where $\langle\cdot\rangle_{\mu,r}$ is the average w.r.t. to the Gibbs measure corresponding to the Gaussian channel $y=\sqrt{r}x^{*}+z$, $x^{*}\sim\mu$ and $z\sim\mathcal{N}(0,1)$. Moreover, if $r>0$, the right-hand side of the above inequality is zero if and only if $\mu=\nu$, i.e., the prior $P_{\textup{{x}}}$ is symmetric.

Finally, the last statement is given here.

Lemma 24.

The map $r\mapsto\operatorname{\mathbb{E}}\left[\left\langle\frac{\mathrm{d}\nu}{\mathrm{d}\mu}(x)-1\right\rangle_{\mu,r}^{2}\right]$ is increasing on $\mathbb{R}_{+}$.

Proof.

This is a matter of showing that the derivative of the above function is non-negative. By standard manipulations (Gaussian integration by parts, Nishimori property), the derivative can be written as

$$\operatorname{\mathbb{E}}\left[\left\langle x\left(\frac{\mathrm{d}\nu}{\mathrm{d}\mu}(x)-1\right)\right\rangle_{\mu,r}^{2}\right].$$

$\blacksquare$

Proof of Proposition 23. The argument relies on a smooth interpolation method between the two measures $\mu$ and $\nu$. Let $t\in[0,1]$ and let $\rho_{t}=(1-t)\mu+t\nu$. Further, let $r,s\geq 0$ be fixed, and

$$\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{3.65486pt}{0.43057pt}}{\psi}(r,s;t):=\operatorname{\mathbb{E}}_{z}\int\left(\log\int\exp\left(\sqrt{r}zx+sxx^{*}-\frac{r}{2}x^{2}\right)\mathrm{d}\rho_{t}(x)\right)\mathrm{d}\rho_{t}(x^{*}),$$

where $z\sim\mathcal{N}(0,1)$. Now let

$$\phi(t)=\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{3.65486pt}{0.43057pt}}{\psi}(r,r;t)-\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{3.65486pt}{0.43057pt}}{\psi}(r,-r;t).$$

We have $\phi(1)=\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{3.65486pt}{0.43057pt}}{\psi}(r,r)-\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{3.65486pt}{0.43057pt}}{\psi}(r,-r)$ on the one hand, and since $\mu$ is a symmetric distribution, $\phi(0)=0$ on the other. We will show that $\phi$ is a convex increasing function on the interval $[0,1]$, strictly so if $\mu\neq\nu$, and that $\phi^{\prime}(0)=0$. Then we deduce that $\phi(1)\geq\frac{\phi^{\prime\prime}(0)}{2}$, allowing us to conclude. First, we have

$$\frac{\mathrm{d}}{\mathrm{d}t}\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{3.65486pt}{0.43057pt}}{\psi}(r,r;t) =\operatorname{\mathbb{E}}_{z}\int\log\int e^{\sqrt{r}zx+rxx^{*}-\frac{r}{2}x^{2}}\mathrm{d}\rho_{t}(x)~{}\mathrm{d}(\nu-\mu)(x^{*})$$

$$~{}~{}~{}+\operatorname{\mathbb{E}}_{z}\int\frac{\int e^{\sqrt{r}zx+rxx^{*}-\frac{r}{2}x^{2}}\mathrm{d}(\nu-\mu)(x)}{\int e^{\sqrt{r}zx+rxx^{*}-\frac{r}{2}x^{2}}\mathrm{d}\rho_{t}(x)}~{}\mathrm{d}\rho_{t}(x^{*}),$$

and

$$\frac{\mathrm{d}^{2}}{\mathrm{d}t^{2}}\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{3.65486pt}{0.43057pt}}{\psi}(r,r;t) =2\operatorname{\mathbb{E}}_{z}\int\frac{\int e^{\sqrt{r}zx+rxx^{*}-\frac{r}{2}x^{2}}\mathrm{d}(\nu-\mu)(x)}{\int e^{\sqrt{r}zx+rxx^{*}-\frac{r}{2}x^{2}}\mathrm{d}\rho_{t}(x)}~{}\mathrm{d}(\nu-\mu)(x^{*})$$

$$~{}~{}~{}-2\operatorname{\mathbb{E}}_{z}\int\left(\frac{\int e^{\sqrt{r}zx+rxx^{*}-\frac{r}{2}x^{2}}\mathrm{d}(\nu-\mu)(x)}{\int e^{\sqrt{r}zx+rxx^{*}-\frac{r}{2}x^{2}}\mathrm{d}\rho_{t}(x)}\right)^{2}~{}\mathrm{d}\rho_{t}(x^{*}).$$

Similar expressions holds for $\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{3.65486pt}{0.43057pt}}{\psi}(r,-r;t)$ where $x^{*}$ is replaced by $-x^{*}$ inside the exponentials. We see from the expression of the first derivative at $t=0$ that $\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{3.65486pt}{0.43057pt}}{\psi}(r,r;0)^{\prime}=\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{3.65486pt}{0.43057pt}}{\psi}(r,-r;0)^{\prime}$. This is because $\rho_{0}=\mu$ is symmetric about the origin, so a sign change (of $x$ for the first term, and $x^{*}$ for the second term in the expression) does not affect the value of the integrals. Hence $\phi^{\prime}(0)=0$. Now, we focus on the second derivative. Observe that since $\mu$ is the symmetric part of $\nu$, $\nu-\mu$ is anti-symmetric. This implies that the first term in the expression of the second derivative changes sign under a sign change in $x^{*}$, and keeps the same modulus. As for the second term, a sign change in $x^{*}$ induces integration against $\mathrm{d}\rho_{t}(-x^{*})$. Hence we can write the difference $(\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{3.65486pt}{0.43057pt}}{\psi}(r,r;t)-\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{3.65486pt}{0.43057pt}}{\psi}(r,-r;t))^{\prime\prime}$ as

$$\frac{\mathrm{d}^{2}}{\mathrm{d}t^{2}}\phi(t) =4\operatorname{\mathbb{E}}_{z}\int\frac{\int e^{\sqrt{r}zx+rxx^{*}-\frac{r}{2}x^{2}}\mathrm{d}(\nu-\mu)(x)}{\int e^{\sqrt{r}zx+rxx^{*}-\frac{r}{2}x^{2}}\mathrm{d}\rho_{t}(x)}~{}\mathrm{d}(\nu-\mu)(x^{*})$$

$$~{}~{}~{}-2\operatorname{\mathbb{E}}_{z}\int\left(\frac{\int e^{\sqrt{r}zx+rxx^{*}-\frac{r}{2}x^{2}}\mathrm{d}(\nu-\mu)(x)}{\int e^{\sqrt{r}zx+rxx^{*}-\frac{r}{2}x^{2}}\mathrm{d}\rho_{t}(x)}\right)^{2}~{}(\mathrm{d}\rho_{t}(x^{*})-\mathrm{d}\rho_{t}(-x^{*})).$$

For any Borel $A$, we have $\rho_{t}(A)-\rho_{t}(-A)=(1-t)(\mu(A)-\mu(-A))+t(\nu(A)-\nu(-A))=2t(\nu-\mu)(A)$. Therefore the second term in the above expression becomes

$$-4t\operatorname{\mathbb{E}}_{z}\int\left(\frac{\int e^{\sqrt{r}zx+rxx^{*}-\frac{r}{2}x^{2}}\mathrm{d}(\nu-\mu)(x)}{\int e^{\sqrt{r}zx+rxx^{*}-\frac{r}{2}x^{2}}\mathrm{d}\rho_{t}(x)}\right)^{2}~{}\mathrm{d}(\nu-\mu)(x^{*}).$$

Since both $\mu$ and $\nu$ are absolutely continuous with respect to $\rho_{t}$ for all $0\leq t<1$ we write

$$\frac{\mathrm{d}^{2}}{\mathrm{d}t^{2}}\phi(t)=4\operatorname{\mathbb{E}}_{z,x^{*}}\left\langle\frac{\mathrm{d}(\nu-\mu)}{\mathrm{d}\rho_{t}}(x)\frac{\mathrm{d}(\nu-\mu)}{\mathrm{d}\rho_{t}}(x^{*})\right\rangle-4t\operatorname{\mathbb{E}}_{z,x^{*}}\left\langle\frac{\mathrm{d}(\nu-\mu)}{\mathrm{d}\rho_{t}}(x)\right\rangle^{2},$$

where the Gibbs average is with respect to the posterior of $x$ given $z,x^{*}$ under the Gaussian channel $y=\sqrt{r}x^{*}+z$, and the expectation is under $x^{*}\sim\rho_{t}$ and $z\sim\mathcal{N}(0,1)$. By the Nishimori property, we simplify the above expression to

$$\frac{\mathrm{d}^{2}}{\mathrm{d}t^{2}}\phi(t)=4(1-t)\operatorname{\mathbb{E}}\left[\left\langle\frac{\mathrm{d}(\nu-\mu)}{\mathrm{d}\rho_{t}}(x)\right\rangle^{2}\right],$$

where the expression is valid for all $0\leq t<1$. From here we see that the function $\phi$ is convex on $[0,1]$ (where we have closed the right end of the interval by continuity). Since $\phi(0)=\phi^{\prime}(0)=0$, $\phi$ is also increasing on $[0,1]$. Therefore we have

$$\phi(1)\geq\frac{1}{2}\phi^{\prime\prime}(0)=2\operatorname{\mathbb{E}}\left[\left\langle\frac{\mathrm{d}\nu}{\mathrm{d}\mu}(x)-1\right\rangle_{\mu,r}^{2}\right].$$

Now it remains to show that if $\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{3.65486pt}{0.43057pt}}{\psi}(r,r)=\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{3.65486pt}{0.43057pt}}{\psi}(r,-r)$ for some $r>0$ then $\mu=\nu$. By the lower bound we have shown, equality of $\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{3.65486pt}{0.43057pt}}{\psi}(r,r)$ and $\makebox[0.0pt][l]{\hskip 2.08334pt\hskip 0.58333pt\rule[8.23611pt]{3.65486pt}{0.43057pt}}{\psi}(r,-r)$ would imply

$$\left\langle\frac{\mathrm{d}\nu}{\mathrm{d}\mu}(x)\right\rangle_{\mu,r}=\frac{\int e^{\sqrt{r}zx+rxx^{*}-\frac{r}{2}x^{2}}\mathrm{d}\nu(x)}{\int e^{\sqrt{r}zx+rxx^{*}-\frac{r}{2}x^{2}}\mathrm{d}\mu(x)}=1$$

for (Lebesgue-)almost all $z$ and $P_{\textup{{x}}}$-almost all $x^{*}$. We make the change of variable $z\mapsto\sqrt{r}(z-x^{*})$ and complete the squares, then the above is equivalent to

$$\int e^{-\frac{r}{2}(x-z)^{2}}\mathrm{d}\nu(x)=\int e^{-\frac{r}{2}(x-z)^{2}}\mathrm{d}\mu(x)$$

for almost all $z$. The above expressions are convolutions of the measures $\nu$ and $\mu$ against the Gaussian kernel. By taking the Fourier transform on both sides and using Fubini’s theorem, we get equality of the characteristic functions of $\mu$ and $\nu$: for all $\xi\in\mathbb{R}$,

$$\int e^{\mathbf{i}\xi x}\mathrm{d}\nu(x)=\int e^{\mathbf{i}\xi x}\mathrm{d}\mu(x).$$

This is because the Fourier transform of the Gaussian (another Gaussian) vanishes nowhere on the real line, thus it can be simplified on both sides. This of course implies that $\nu=\mu$, and concludes our proof.  

Acknowledgments. AE is grateful to Léo Miolane for insightful conversations. This research effort was initiated at the Workshop on Statistical physics, Learning, Inference and Networks at Ecole de Physique des Houches, winter 2017. FK acknowledges funding from the EU (FP/2007-2013/ERC grant agreement 307087-SPARCS). MJ acknowledges the support of the Mathematical Data Science program of the Office of Naval Research under grant number N00014-15-1-2670.